两个数组的最小乘积和

Submission

运行时间: 89 ms

内存: 21.1 MB

class Solution:
    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:
        # nums1.sort()
        # index = sorted(range(len(nums1)), key = lambda x: nums2[x], reverse = True)
        # return sum(x * nums2[y] for x, y in zip(nums1, index))
        num1 = [0] * 100
        num2 = [0] * 100
        for n1, n2 in zip(nums1, nums2):
            num1[n1-1] += 1
            num2[n2-1] += 1
        
        ans = 0
        L, R = 0, 99
        while R >= 0:
            cnt = min(num1[L], num2[R])
            ans += cnt * (L+1) * (R+1)
            num1[L] -= cnt
            num2[R] -= cnt
            while L < 100 and num1[L] == 0:    L += 1
            while R >= 0 and num2[R] == 0:    R -= 1
        return ans

Explain

题解的核心思想是利用计数排序的方式来避免对原始数组进行排序，从而在一定程度上优化时间复杂度。具体而言，题解创建了两个长度为100的数组num1和num2，用来计数nums1和nums2中各个元素的出现次数（假设元素大小在1到100之间）。然后，使用双指针方法，一个指针L从前向后遍历num1，另一个指针R从后向前遍历num2，这样可以保证乘积尽可能小。每一步中，计算可以配对的元素的数量（即两个计数中的最小值），并累加到结果中。指针移动至下一个非零计数位置继续配对，直到一个数组完全被遍历完毕。

时间复杂度: O(n + 100) = O(n)

空间复杂度: O(100) = O(1)

class Solution:
    def minProductSum(self, nums1: List[int], nums2: List[int]) -> int:
        num1 = [0] * 100  # 计数数组，记录nums1中元素的频率
        num2 = [0] * 100  # 计数数组，记录nums2中元素的频率
        for n1, n2 in zip(nums1, nums2):
            num1[n1-1] += 1  # 对应元素频率+1
            num2[n2-1] += 1  # 对应元素频率+1
        
        ans = 0  # 初始化最小乘积和
        L, R = 0, 99  # 双指针初始化
        while R >= 0:
            cnt = min(num1[L], num2[R])  # 找到当前两个元素的最小配对数量
            ans += cnt * (L+1) * (R+1)  # 计算当前配对的乘积和，累加到结果中
            num1[L] -= cnt  # 更新计数数组
            num2[R] -= cnt  # 更新计数数组
            while L < 100 and num1[L] == 0: L += 1  # 移动L指针到下一个非零元素
            while R >= 0 and num2[R] == 0: R -= 1  # 移动R指针到下一个非零元素
        return ans  # 返回最终的最小乘积和

Explore

计数排序被选用是因为它相比于传统的比较排序（如快速排序、归并排序等）在特定条件下有更低的时间复杂度。当输入的数字范围有限且固定（如1到100）时，计数排序的时间复杂度可以达到O(n)，而传统排序算法的时间复杂度通常为O(n log n)。这种优化尤其在面对大量数据时显著，因此，在已知数据范围的情况下使用计数排序可以更有效率地处理数据。

在双指针法中，指针L从前向后移动，而指针R从后向前移动，这种策略确保了较小的数与较大的数相乘。由于L指针代表较小的数，R指针代表较大的数，这种配对方式可以使得乘积和尽可能小。通过选择最小的计数来配对，然后更新计数并适当移动指针，这种方法不断寻找当前可能的最小乘积和，从而确保了整体乘积和的最小性。

如果元素的范围变化，计数排序的数组长度应相应调整来匹配新的范围。例如，如果元素范围是1到500，计数数组的大小应扩展到500。对于更窄的范围，数组大小也应相应减小。此外，如果数据范围极大或不连续，可能需要考虑使用哈希表来进行计数，以保持空间效率和处理速度。

计数数组的长度选择为100是因为题目设定了元素大小在1到100之间。这意味着算法是专门为这一特定范围优化的。在应用到其他范围的数据时，算法需要相应调整计数数组的大小来适应新的元素范围。因此，虽然算法在当前形式下只适用于特定范围的数组，但通过调整可以使其适用于更广泛的情况。