class Solution {
public:
int minProductSum(vector<int>& nums1, vector<int>& nums2) {
}
};
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.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 100原站题解
golang 解法, 执行用时: 176 ms, 内存消耗: 9.2 MB, 提交时间: 2023-10-16 21:05:04
func minProductSum(nums1 []int, nums2 []int) int {
sort.Ints(nums1)
sort.Ints(nums2)
ans:=0
n:=len(nums1)
for i:=0;i<n;i++{
ans+=nums1[i]*nums2[n-i-1]
}
return ans
}
rust 解法, 执行用时: 44 ms, 内存消耗: 3.5 MB, 提交时间: 2023-10-16 21:04:37
impl Solution {
pub fn min_product_sum(mut nums1: Vec<i32>, mut nums2: Vec<i32>) -> i32 {
nums1.sort();
nums2.sort_by(|a, b| b.cmp(a));
let mut sum = 0;
for i in 0..nums1.len() {
sum += nums1[i] * nums2[i];
}
sum
}
}
python3 解法, 执行用时: 156 ms, 内存消耗: 22.1 MB, 提交时间: 2023-10-16 21:04:28
class Solution:
def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:
return sum(x * y for x, y in zip(sorted(nums1), sorted(nums2, reverse=True)))
cpp 解法, 执行用时: 168 ms, 内存消耗: 103.4 MB, 提交时间: 2023-10-16 21:03:42
class Solution {
public:
int minProductSum(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end(),greater<int>());
int ans = 0;
for(int i =0;i<nums1.size();i++){
ans+=nums1[i]*nums2[i];
}
return ans;
}
};
java 解法, 执行用时: 24 ms, 内存消耗: 52.8 MB, 提交时间: 2023-10-16 21:03:26
class Solution {
public int minProductSum(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int len = nums1.length;
boolean isAdd = false;
if(len % 2 != 0) {
isAdd = true;
}
int res = 0;
int i = 0, j = nums1.length - 1;
for(; i < j; ++i, --j) {
res += nums1[i] * nums2[j];
}
i = 0;
j = nums1.length - 1;
for(; i < j; ++i, --j) {
res += nums2[i] * nums1[j];
}
if(isAdd) {
res += nums1[i] * nums2[i];
}
return res;
}
}