Medium

题目描述

给你两个长度为 n 的整数数组 nums1 和 nums2，以及一个整数 k。你可以对 nums1 执行以下操作：

  • 选择两个下标 i 和 j，使 nums1[i] 增加 k，nums1[j] 减少 k。换句话说，nums1[i] = nums1[i] + k 且 nums1[j] = nums1[j] - k。

如果对于所有满足 0 <= i < n 的下标 i，都有 nums1[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 <= 10^5
  • 0 <= nums1[i], nums2[j] <= 10^9
  • 0 <= k <= 10^5

解题思路

这道题是一个贪心问题，需要分析操作的本质和不可能情况。

核心思路：

  1. 分析操作特性：每次操作会选择两个位置，一个增加k，一个减少k，因此数组总和保持不变。如果 nums1 和 nums2 的总和不相等，直接返回 -1。

  2. 特殊情况处理：当 k = 0 时，无法进行任何修改，只能检查两数组是否已经相等。

  3. 差值分析：对于每个位置 i，计算差值 diff[i] = nums2[i] - nums1[i]。要使数组相等，需要将所有差值变为 0。

  4. 可行性检查：由于每次操作只能改变 k 的倍数，所有差值都必须是 k 的倍数，否则无法实现。

  5. 最优策略：将需要增加的位置和需要减少的位置进行匹配。计算总的增加量（或减少量），由于每次操作处理 k 个单位，所以操作次数就是总增加量除以 k。

算法步骤：

  • 首先检查总和是否相等
  • 处理 k = 0 的特殊情况
  • 计算每个位置的差值，检查是否都是 k 的倍数
  • 计算需要增加的总量，即为最少操作次数

代码实现

class Solution {
public:
    long long minOperations(vector<int>& nums1, vector<int>& nums2, int k) {
        int n = nums1.size();
        
        // 计算总和差值
        long long sum1 = 0, sum2 = 0;
        for (int i = 0; i < n; i++) {
            sum1 += nums1[i];
            sum2 += nums2[i];
        }
        
        // 如果总和不相等，无法通过操作使数组相等
        if (sum1 != sum2) return -1;
        
        // 特殊情况：k = 0
        if (k == 0) {
            for (int i = 0; i < n; i++) {
                if (nums1[i] != nums2[i]) return -1;
            }
            return 0;
        }
        
        long long totalInc = 0;
        
        // 检查每个位置的差值
        for (int i = 0; i < n; i++) {
            int diff = nums2[i] - nums1[i];
            
            // 差值必须是k的倍数
            if (diff % k != 0) return -1;
            
            // 累计需要增加的总量
            if (diff > 0) {
                totalInc += diff / k;
            }
        }
        
        return totalInc;
    }
};

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:
        n = len(nums1)
        
        # 计算总和差值
        sum1, sum2 = sum(nums1), sum(nums2)
        
        # 如果总和不相等，无法通过操作使数组相等
        if sum1 != sum2:
            return -1
        
        # 特殊情况：k = 0
        if k == 0:
            return 0 if nums1 == nums2 else -1
        
        total_inc = 0
        
        # 检查每个位置的差值
        for i in range(n):
            diff = nums2[i] - nums1[i]
            
            # 差值必须是k的倍数
            if diff % k != 0:
                return -1
            
            # 累计需要增加的总量
            if diff > 0:
                total_inc += diff // k
        
        return total_inc

public class Solution {
    public long MinOperations(int[] nums1, int[] nums2, int k) {
        int n = nums1.Length;
        
        // 计算总和差值
        long sum1 = 0, sum2 = 0;
        for (int i = 0; i < n; i++) {
            sum1 += nums1[i];
            sum2 += nums2[i];
        }
        
        // 如果总和不相等，无法通过操作使数组相等
        if (sum1 != sum2) return -1;
        
        // 特殊情况：k = 0
        if (k == 0) {
            for (int i = 0; i < n; i++) {
                if (nums1[i] != nums2[i]) return -1;
            }
            return 0;
        }
        
        long totalInc = 0;
        
        // 检查每个位置的差值
        for (int i = 0; i < n; i++) {
            long diff = (long)nums2[i] - nums1[i];
            
            // 差值必须是k的倍数
            if (diff % k != 0) return -1;
            
            // 累计需要增加的总量
            if (diff > 0) {
                totalInc += diff / k;
            }
        }
        
        return totalInc;
    }
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number}
 */
var minOperations = function(nums1, nums2, k) {
    const n = nums1.length;
    
    if (k === 0) {
        for (let i = 0; i < n; i++) {
            if (nums1[i] !== nums2[i]) return -1;
        }
        return 0;
    }
    
    let totalDiff = 0;
    let positiveOps = 0;
    
    for (let i = 0; i < n; i++) {
        const diff = nums2[i] - nums1[i];
        
        if (diff % k !== 0) return -1;
        
        totalDiff += diff;
        if (diff > 0) {
            positiveOps += diff / k;
        }
    }
    
    if (totalDiff !== 0) return -1;
    
    return positiveOps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，需要遍历数组一次计算总和，再遍历一次处理差值
空间复杂度O(1)，只使用常数个额外变量

相关题目