两个数组的最小乘积和
难度:
标签:
题目描述
代码结果
运行时间: 89 ms, 内存: 21.1 MB
/*
题目思路:
通过 Java Stream API,可以使用流的方式进行排序和遍历。将 nums1 升序,nums2 降序后,使用 IntStream 进行乘积计算并求和。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public int minProductSumStream(int[] nums1, int[] nums2) {
Arrays.sort(nums1); // 将第一个数组升序排序
Arrays.sort(nums2); // 将第二个数组升序排序
int n = nums1.length;
// 使用 IntStream 计算最小乘积和
return IntStream.range(0, n)
.map(i -> nums1[i] * nums2[n - 1 - i]) // 计算每一对的乘积
.sum(); // 求和并返回结果
}
解释
方法:
题解的核心思想是利用计数排序的方式来避免对原始数组进行排序,从而在一定程度上优化时间复杂度。具体而言,题解创建了两个长度为100的数组num1和num2,用来计数nums1和nums2中各个元素的出现次数(假设元素大小在1到100之间)。然后,使用双指针方法,一个指针L从前向后遍历num1,另一个指针R从后向前遍历num2,这样可以保证乘积尽可能小。每一步中,计算可以配对的元素的数量(即两个计数中的最小值),并累加到结果中。指针移动至下一个非零计数位置继续配对,直到一个数组完全被遍历完毕。
时间复杂度:
O(n + 100) = O(n)
空间复杂度:
O(100) = O(1)
代码细节讲解
🦆
为什么使用计数排序而不是直接对nums1和nums2进行排序来找到最小乘积和?
▷🦆
在双指针法中,指针L和R的移动策略是如何确保总是得到最小乘积和的?
▷🦆
如果元素的范围不是1到100,而是更广或更窄,这种方法应如何调整?
▷🦆
题解中的计数数组为什么选择长度为100,这是否意味着算法只适用于元素值在特定范围内的数组?
▷