leetcode
leetcode 1701 ~ 1750
两个数组的最小乘积和

两个数组的最小乘积和

难度:

标签:

题目描述

代码结果

运行时间: 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进行排序来找到最小乘积和?
计数排序被选用是因为它相比于传统的比较排序(如快速排序、归并排序等)在特定条件下有更低的时间复杂度。当输入的数字范围有限且固定(如1到100)时,计数排序的时间复杂度可以达到O(n),而传统排序算法的时间复杂度通常为O(n log n)。这种优化尤其在面对大量数据时显著,因此,在已知数据范围的情况下使用计数排序可以更有效率地处理数据。
🦆
在双指针法中,指针L和R的移动策略是如何确保总是得到最小乘积和的?
在双指针法中,指针L从前向后移动,而指针R从后向前移动,这种策略确保了较小的数与较大的数相乘。由于L指针代表较小的数,R指针代表较大的数,这种配对方式可以使得乘积和尽可能小。通过选择最小的计数来配对,然后更新计数并适当移动指针,这种方法不断寻找当前可能的最小乘积和,从而确保了整体乘积和的最小性。
🦆
如果元素的范围不是1到100,而是更广或更窄,这种方法应如何调整?
如果元素的范围变化,计数排序的数组长度应相应调整来匹配新的范围。例如,如果元素范围是1到500,计数数组的大小应扩展到500。对于更窄的范围,数组大小也应相应减小。此外,如果数据范围极大或不连续,可能需要考虑使用哈希表来进行计数,以保持空间效率和处理速度。
🦆
题解中的计数数组为什么选择长度为100,这是否意味着算法只适用于元素值在特定范围内的数组?
计数数组的长度选择为100是因为题目设定了元素大小在1到100之间。这意味着算法是专门为这一特定范围优化的。在应用到其他范围的数据时,算法需要相应调整计数数组的大小来适应新的元素范围。因此,虽然算法在当前形式下只适用于特定范围的数组,但通过调整可以使其适用于更广泛的情况。

相关问题