最小差值平方和

标签: 数组 数学 排序 堆（优先队列）

难度: Medium

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度为 n 。

数组 nums1 和 nums2 的 差值平方和 定义为所有满足 0 <= i < n 的 (nums1[i] - nums2[i])2 之和。

同时给你两个正整数 k1 和 k2 。你可以将 nums1 中的任意元素 +1 或者 -1 至多 k1 次。类似的，你可以将 nums2 中的任意元素 +1 或者 -1 至多 k2 次。

请你返回修改数组 nums1 至多 k1 次且修改数组 nums2 至多 k2 次后的最小 差值平方和 。

注意：你可以将数组中的元素变成 负 整数。

示例 1：

输入：nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0
输出：579
解释：nums1 和 nums2 中的元素不能修改，因为 k1 = 0 和 k2 = 0 。
差值平方和为：(1 - 2)2 + (2 - 10)2 + (3 - 20)2 + (4 - 19)2 = 579 。

示例 2：

输入：nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
输出：43
解释：一种得到最小差值平方和的方式为：
- 将 nums1[0] 增加一次。
- 将 nums2[2] 增加一次。
最小差值平方和为：
(2 - 5)2 + (4 - 8)2 + (10 - 7)2 + (12 - 9)2 = 43 。
注意，也有其他方式可以得到最小差值平方和，但没有得到比 43 更小答案的方案。

提示：

  • n == nums1.length == nums2.length
  • 1 <= n <= 105
  • 0 <= nums1[i], nums2[i] <= 105
  • 0 <= k1, k2 <= 109

Submission

运行时间: 116 ms

内存: 31.2 MB

class Solution:
    def minSumSquareDiff(self, nums1: List[int], nums2: List[int], k1: int, k2: int) -> int:
        k = k1+k2 
        n = len(nums1)
        nums = []
        for i in range(n):
            nums.append(abs(nums1[i]-nums2[i]))
        nums.sort(reverse = True)
        nums.append(0)
        up = nums[0]
        remainder = 0
        for i in range(n):
            diff = (i+1)*(nums[i]-nums[i+1])
            if diff <= k:
                k -= diff 
                up = nums[i+1]
            else:
              
                t = k//(i+1)
                up = nums[i] - t
                remainder = k%(i+1)
                break 
     
        ans = 0
        
        ans += up*up*(i+1-remainder)
        ans += (up-1)*(up-1)*(remainder)
        for j in range(i+1,n):
           
            ans += nums[j]*nums[j]
        return ans

Explain

首先，计算两个数组中对应元素的差的绝对值，并将这些差值存储在一个列表中。然后对这个差值列表进行降序排序，以便优先考虑减少最大差值的平方。接着，尝试使用可用的操作次数（k1 + k2）来减少这些差值。从最大的差值开始，一步一步使用操作次数来尽量减少差值。如果所有的操作次数用完或者差值已经减至最小（即为0），则退出。最后，计算调整后的差值平方和。这种方法通过优先减少最大的差值，来尽可能降低总的差值平方和。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def minSumSquareDiff(self, nums1: List[int], nums2: List[int], k1: int, k2: int) -> int:
        k = k1 + k2  # 综合两数组的可调整次数
        n = len(nums1)
        nums = []
        for i in range(n):
            nums.append(abs(nums1[i] - nums2[i]))  # 计算并存储差值的绝对值
        nums.sort(reverse=True)  # 降序排序差值
        nums.append(0)  # 添加一个边界值以方便处理
        up = nums[0]
        remainder = 0
        for i in range(n):
            diff = (i + 1) * (nums[i] - nums[i + 1])
            if diff <= k:
                k -= diff  # 使用部分操作次数减小差值
                up = nums[i + 1]
            else:
                t = k // (i + 1)
                up = nums[i] - t
                remainder = k % (i + 1)
                break  # 操作次数不足以继续减少当前差值
        ans = 0
        ans += up * up * (i + 1 - remainder)  # 计算调整后的平方和
        ans += (up - 1) * (up - 1) * remainder
        for j in range(i + 1, n):
            ans += nums[j] * nums[j]  # 对于未调整的差值，直接计算平方和
        return ans

Explore

在题解中，选择将差值数组进行降序排序是为了优先减少最大的差值。由于目标是最小化所有差值的平方和，而平方函数是一个非线性增长的函数，因此较大的差值对总平方和的贡献更大。通过优先减少这些较大的差值，可以更有效地减少总的平方和。这种排序方式使得可以更有策略地使用有限的操作次数，以实现对总平方和的最大可能降低。

题解中的方法在操作次数不足以继续减少当前的最大差值时确实停止了进一步的减少，并进行了一次均匀分配，使得剩余的操作次数尽可能均匀地分配在当前未处理的最大差值上。虽然这种方法简化了处理流程，并在很多情况下能有效地减少平方和，但它可能不是在所有情况下都最优的。例如，可能存在通过将所有剩余操作次数集中在少数几个较大的差值上，而不是均匀分配，能够得到更小的总平方和的情况。

在实现中添加`nums.append(0)`作为边界值是为了处理所有差值都被减至0或当操作次数用完时的情况。这个边界值简化了循环和条件判断，使得在减少最后一个差值时不需要特别处理数组越界的问题。它确保了在减少每个差值时可以方便地引用`nums[i+1]`，并正确计算接下来需要减少的差值数量，避免了代码中可能出现的错误和复杂性。

题解中将操作次数`k`视为`k1 + k2`的总和，确实意味着在调整过程中不区分修改`nums1`或`nums2`的次数限制。这种处理方式简化了问题的解决方案，因为它假设所有的操作次数可以自由地用于任一数组的任一位置。然而，这种策略可能不总是最优的，尤其是在实际应用中如果修改`nums1`和`nums2`的成本或影响不同，或者存在某些额外的约束条件时。在这种情况下，可能需要更精细的策略来区分和优化每个数组的修改次数的使用。