LeetCode 2333. 最小差值平方和（贪心）

Michael阿明

发布于 2022-07-31 01:34:36

36600

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

文章目录
1. 题目
2. 解题

1. 题目

给你两个下标从 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 <= 10^5
0 <= nums1[i], nums2[i] <= 10^5
0 <= k1, k2 <= 10^9

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/minimum-sum-of-squared-difference 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

答案只与对应元素的非零绝对值有关系
对这些绝对值进行排序，大的优先减少

class Solution:
    def minSumSquareDiff(self, nums1: List[int], nums2: List[int], k1: int, k2: int) -> int:
        diff = list(filter(lambda x : x!=0, [abs(x-y) for x, y in zip(nums1, nums2)]))
        # 非零 绝对值
        diff.sort(reverse=True) # 逆序排列
        if len(diff) == 0:
            return 0
        k = k1+k2  # 总的调整次数
        diff.append(0)  # 代码编写简单需要
        prevnum = diff[0]
        ct = 1 # 前面相同元素的个数
        i = 0
        while i < len(diff)-1:
            delta = diff[i]-diff[i+1] # 跟后一个的差值
            if delta == 0:
                ct += 1  # 相同值的元素个数 + 1
            else: # 遇到有下降台阶了
                if k >= delta*ct: # k 的次数，够ct个数降到下个元素的值
                    prevnum = diff[i+1]
                    k -= delta*ct
                    ct += 1
                else:  # 不够， 结束了
                    delta = k//ct  # 把剩余的 k 次 均匀分给 ct 个数
                    prevnum -= delta # 每个数还能降低 delta
                    left = k - delta*ct # 剩余的次数，每个数的值还能 -1
                    return int(math.pow((prevnum-1), 2)*left + math.pow(prevnum, 2)*(ct-left) + sum([x*x for x in diff[ct:]]))
            i += 1
        return 0