跳转至

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

题目描述

给定两个长度相等的数组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 <= 105
  • 1 <= nums1[i], nums2[i] <= 100

解法

方法一：贪心 + 排序

思考

两数组对应相乘再求和，其中一个可任意重排，求最小乘积和。正数情形下，大数应配小数。

将 \(nums1\) 升序、\(nums2\) 降序后对应相乘累加，即重新排列中的最小点积。

由于两个数组都是正整数，要使得乘积和最小，我们可以将两个数组中的最大值和最小值相乘，次大值和次小值相乘，以此类推。

因此，我们将数组 \(\textit{nums1}\) 按照升序排序，将数组 \(\textit{nums2}\) 按照降序排序，然后将两个数组对应位置的元素相乘，累加即可。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 是数组 \(\textit{nums1}\) 的长度。

1
2
3
4
5
class Solution:
    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:
        nums1.sort()
        nums2.sort(reverse=True)
        return sum(x * y for x, y in zip(nums1, nums2))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int minProductSum(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int n = nums1.length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += nums1[i] * nums2[n - i - 1];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int minProductSum(vector<int>& nums1, vector<int>& nums2) {
        ranges::sort(nums1);
        ranges::sort(nums2, greater<int>());
        int n = nums1.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += nums1[i] * nums2[i];
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func minProductSum(nums1 []int, nums2 []int) (ans int) {
    sort.Ints(nums1)
    sort.Ints(nums2)
    for i, x := range nums1 {
        ans += x * nums2[len(nums2)-1-i]
    }
    return
}

1
2
3
4
5
6
7
8
9
function minProductSum(nums1: number[], nums2: number[]): number {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => b - a);
    let ans = 0;
    for (let i = 0; i < nums1.length; ++i) {
        ans += nums1[i] * nums2[i];
    }
    return ans;
}

评论