LeetCode 1874. 兩個數組的最小乘積和

Michael阿明 2021-08-15 22:28:24 阅读数:430

本文一共[544]字,预计阅读时长:1分钟~
leetcode 最小 小乘

文章目錄

1. 題目

給定兩個長度相等的數組a和b,它們的乘積和為數組中所有的a[i] * b[i]之和,其中 0 <= i < a.length

比如a = [1,2,3,4],b = [5,2,3,1]時,它們的乘積和為 1*5 + 2*2 + 3*3 + 4*1 = 22

現有兩個長度都為 n 的數組 nums1和nums2,你可以以任意順序排序nums1,請返回它們的最小乘積和

示例 1:
輸入: nums1 = [5,3,4,2], nums2 = [4,2,2,5]
輸出: 40
解釋: 將 num1 重新排列為 [3,5,4,2] 後,
可由 [3,5,4,2][4,2,2,5] 得到最小乘積和 3*4 + 5*2 + 4*2 + 2*5 = 40。
示例 2:
輸入: nums1 = [2,1,4,5,7], nums2 = [3,2,4,8,6]
輸出: 65
解釋: 將 num1 重新排列為 [5,7,4,1,2] 後,
可由 [5,7,4,1,2][3,2,4,8,6] 得到最小乘積和 5*3 + 7*2 + 4*4 + 1*8 + 2*6 = 65。
提示:
n == nums1.length == nums2.length
1 <= n <= 10^5
1 <= nums1[i], nums2[i] <= 100

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/minimize-product-sum-of-two-arrays
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。

2. 解題

  • a > b , c > d a > b, c > d a>b,c>d a c + b d , a d + b c ac+bd, ad+bc ac+bdad+bc 兩種選擇
  • a c + b d − a d − b c = a ( c − d ) − b ( c − d ) = ( a − b ) ( c − d ) > 0 → a c + b d > a d + b c ac+bd-ad-bc=a(c-d)-b(c-d)=(a-b)(c-d) > 0 \rightarrow ac+bd > ad+bc ac+bdadbc=a(cd)b(cd)=(ab)(cd)>0ac+bd>ad+bc,最大的乘以最小的會得到更小的結果
class Solution {

public:
int minProductSum(vector<int>& nums1, vector<int>& nums2) {

// a > b, c > d
// ac+bd-ad-bc=a(c-d)-b(c-d) > 0
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
int ans = 0, n = nums1.size();
for(int i = 0; i < n; ++i)
ans += nums1[i]*nums2[n-1-i];
return ans;
}
};

156 ms 102.9 MB C++


我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號(Michael阿明),一起加油、一起學習進步!
Michael阿明

版权声明:本文为[Michael阿明]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815222753145B.html