LeetCode 1874. 两个数组的最小乘积和

Michael阿明

发布于 2021-09-06 11:38:05

5470

发布于 2021-09-06 11:38:05

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

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. 解题

ac+bd，ad+bc 两种选择
ac+bd−ad−bc=a(c−d)−b(c−d)=(a−b)(c−d)>0→ac+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阿明），一起加油、一起学习进步！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/08/15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https