使数组中所有元素相等的最小操作数 II

标签: 贪心 数组 数学

难度: Medium

给你两个整数数组 nums1 和 nums2 ，两个数组长度都是 n ，再给你一个整数 k 。你可以对数组 nums1 进行以下操作：

  • 选择两个下标 i 和 j ，将 nums1[i] 增加 k ，将 nums1[j] 减少 k 。换言之，nums1[i] = nums1[i] + k 且 nums1[j] = nums1[j] - k 。

如果对于所有满足 0 <= i < n 都有 num1[i] == nums2[i] ，那么我们称 nums1 等于 nums2 。

请你返回使 nums1 等于 nums2 的 最少 操作数。如果没办法让它们相等，请你返回 -1 。

示例 1：

输入：nums1 = [4,3,1,4], nums2 = [1,3,7,1], k = 3
输出：2
解释：我们可以通过 2 个操作将 nums1 变成 nums2 。
第 1 个操作：i = 2 ，j = 0 。操作后得到 nums1 = [1,3,4,4] 。
第 2 个操作：i = 2 ，j = 3 。操作后得到 nums1 = [1,3,7,1] 。
无法用更少操作使两个数组相等。

示例 2：

输入：nums1 = [3,8,5,2], nums2 = [2,4,1,6], k = 1
输出：-1
解释：无法使两个数组相等。

提示：

  • n == nums1.length == nums2.length
  • 2 <= n <= 105
  • 0 <= nums1[i], nums2[j] <= 109
  • 0 <= k <= 105

Submission

运行时间: 55 ms

内存: 29.9 MB

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:
        ans = sum = 0
        for x, y in zip(nums1, nums2):
            x -= y
            if k:
                if x % k: return -1
                sum += x // k
                if x > 0: ans += x // k
            elif x: return -1
        return -1 if sum else ans

Explain

题解的核心思想是首先计算两个数组中对应位置元素的差值，并检查这些差值是否能被k整除。若不能整除，则直接返回-1，因为不能通过指定操作使两数组相等。如果能整除，则计算每个位置需要的操作次数（差值除以k的商），并累加。特别地，对于所有正差值的累加总和（即需要增加的总次数），单独计算为变量ans。若总操作次数为0，说明两数组已相等，返回ans；否则返回-1。

时间复杂度: O(n)

空间复杂度: O(1)

# 定义解决方案类
class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:
        ans = 0  # 存储所需的操作总次数
        sum = 0  # 存储所有差值除以k的商的和
        for x, y in zip(nums1, nums2):  # 遍历两数组的元素
            x -= y  # 计算差值
            if k:  # 如果k不为0
                if x % k: return -1  # 差值不是k的倍数，无法通过加减k操作达成
                sum += x // k  # 计算差值的商，并累加到sum
                if x > 0: ans += x // k  # 对于正差值，累加到ans
            elif x: return -1  # 如果k为0且存在非零差值，直接返回-1
        return -1 if sum else ans  # 如果总操作次数不为0，返回-1，否则返回ans

Explore

在题解中，如果差值不是k的倍数，则无法通过添加或减少k的倍数的方式使两个元素相等。这是因为每次操作只能增加或减少k，因此任何不是k的倍数的差值都无法恰好通过这种操作方式调整为0。因此，如果存在任何一个差值不是k的倍数，整个数组调整任务就不可能完成，所以直接返回-1是正确的处理方式。

在题解中，如果差值x为正，表示需要增加元素的值来匹配另一数组中的对应元素。故累加正差值的操作次数到变量ans。对于负差值（即x < 0），这表示需要减少元素的值，此时x // k将自动得到一个负数，这种操作会在变量sum中被累加，但不直接影响ans，因为ans只计算增加操作的次数。

是的，算法中的`sum += x // k`确实考虑了累加的正负号。这里的sum变量累加了所有差值除以k的商，包括正数和负数。最终，算法检查sum是否为0来确定是否所有的操作（增加与减少）彼此抵消，仅在sum为0（即所有操作相互抵消，数组已经平衡）时返回ans，否则返回-1。

这个条件检查的是k为0的情况下，是否存在非零差值。如果k为0，表明不能通过增加或减少任何值（因为0乘以任何数都是0）来调整数组元素的值。因此，如果存在任何非零差值，这意味着两个元素无法通过任何操作变得相等，因此返回-1。这是因为在没有有效操作（操作数k为0）的条件下，任何非零差值都说明数组无法调整为全等。