Medium

题目描述

给你两个长度可能不等的整数数组 nums1 和 nums2。两个数组中的所有值都在 1 到 6 之间（包含 1 和 6）。

每次操作中，你可以选择 任意 数组中的任意一个整数，将它变成 1 到 6 之间 任意 的值（包含 1 和6）。

请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等，请返回 -1。

示例 1：

输入：nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums2[0] 改为 6 。 nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[5] 改为 1 。 nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2] 。  
- 将 nums1[2] 改为 2 。 nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2] 。

示例 2：

输入：nums1 = [1,1,1,1,1,1,1], nums2 = [6]
输出：-1
解释：没有办法减少 nums1 的和或者增加 nums2 的和使它们相等。

示例 3：

输入：nums1 = [6,6], nums2 = [1]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums1[0] 改为 2 。 nums1 = [2,6], nums2 = [1] 。
- 将 nums1[1] 改为 2 。 nums1 = [2,2], nums2 = [1] 。
- 将 nums2[0] 改为 4 。 nums1 = [2,2], nums2 = [4] 。

提示：

  • 1 <= nums1.length, nums2.length <= 10^5
  • 1 <= nums1[i], nums2[i] <= 6

解题思路

解题思路

这道题的关键在于贪心策略：我们需要尽可能高效地改变数组元素，使两个数组的和相等。

核心观察：

  1. 每个数字的值域是 [1,6]，所以每次操作最多能改变的差值是 5
  2. 对于和较大的数组，我们应该将较大的数字改小；对于和较小的数组，我们应该将较小的数字改大
  3. 为了最小化操作次数，我们应该贪心地选择能产生最大差值变化的操作

算法流程：

  1. 计算两个数组的和，如果相等直接返回 0
  2. 确保 nums1 是和较小的数组，nums2 是和较大的数组（便于统一处理）
  3. 计算需要缩小的差值
  4. 统计每种可能的差值变化量的出现次数：
    • 对于和较小的数组，数字 x 最多能增加 6-x
    • 对于和较大的数组，数字 x 最多能减少 x-1
  5. 按照差值变化量从大到小贪心选择，直到差值为 0

边界判断：

  • 如果一个数组全是 6，另一个数组全是 1，仍无法相等，则返回 -1
  • 具体判断：sum1 + nums1.length * 5 < sum2 - nums2.length * 5

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
        int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
        
        if (sum1 == sum2) return 0;
        
        // 确保 nums1 是和较小的数组
        if (sum1 > sum2) {
            swap(nums1, nums2);
            swap(sum1, sum2);
        }
        
        int diff = sum2 - sum1;
        
        // 检查是否可能相等
        if (sum1 + nums1.size() * 5 < sum2 - nums2.size() * 5) {
            return -1;
        }
        
        // 统计每种差值变化量的出现次数
        vector<int> changes(6, 0);
        
        // nums1 中的数字可以增加
        for (int x : nums1) {
            changes[6 - x]++;
        }
        
        // nums2 中的数字可以减少
        for (int x : nums2) {
            changes[x - 1]++;
        }
        
        // 贪心选择最大的差值变化
        int operations = 0;
        for (int change = 5; change >= 1 && diff > 0; change--) {
            int count = min(changes[change], (diff + change - 1) / change);
            operations += count;
            diff -= count * change;
        }
        
        return operations;
    }
};

class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
        sum1, sum2 = sum(nums1), sum(nums2)
        
        if sum1 == sum2:
            return 0
        
        # 确保 nums1 是和较小的数组
        if sum1 > sum2:
            nums1, nums2 = nums2, nums1
            sum1, sum2 = sum2, sum1
        
        diff = sum2 - sum1
        
        # 检查是否可能相等
        if sum1 + len(nums1) * 5 < sum2 - len(nums2) * 5:
            return -1
        
        # 统计每种差值变化量的出现次数
        changes = [0] * 6
        
        # nums1 中的数字可以增加
        for x in nums1:
            changes[6 - x] += 1
        
        # nums2 中的数字可以减少
        for x in nums2:
            changes[x - 1] += 1
        
        # 贪心选择最大的差值变化
        operations = 0
        for change in range(5, 0, -1):
            if diff <= 0:
                break
            count = min(changes[change], (diff + change - 1) // change)
            operations += count
            diff -= count * change
        
        return operations

public class Solution {
    public int MinOperations(int[] nums1, int[] nums2) {
        int sum1 = nums1.Sum();
        int sum2 = nums2.Sum();
        
        if (sum1 == sum2) return 0;
        
        // 确保 nums1 是和较小的数组
        if (sum1 > sum2) {
            (nums1, nums2) = (nums2, nums1);
            (sum1, sum2) = (sum2, sum1);
        }
        
        int diff = sum2 - sum1;
        
        // 检查是否可能相等
        if (sum1 + nums1.Length * 5 < sum2 - nums2.Length * 5) {
            return -1;
        }
        
        // 统计每种差值变化量的出现次数
        int[] changes = new int[6];
        
        // nums1 中的数字可以增加
        foreach (int x in nums1) {
            changes[6 - x]++;
        }
        
        // nums2 中的数字可以减少
        foreach (int x in nums2) {
            changes[x - 1]++;
        }
        
        // 贪心选择最大的差值变化
        int operations = 0;
        for (int change = 5; change >= 1 && diff > 0; change--) {
            int count = Math.Min(changes[change], (diff + change - 1) / change);
            operations += count;
            diff -= count * change;
        }
        
        return operations;
    }
}

var minOperations = function(nums1, nums2) {
    const sum1 = nums1.reduce((a, b) => a + b, 0);
    const sum2 = nums2.reduce((a, b) => a + b, 0);
    
    if (sum1 === sum2) return 0;
    
    // Check if it's possible
    const min1 = nums1.length;
    const max1 = nums1.length * 6;
    const min2 = nums2.length;
    const max2 = nums2.length * 6;
    
    if (Math.max(min1, min2) > Math.min(max1, max2)) return -1;
    
    // Make sure nums1 has the smaller sum
    let smaller, larger, smallerSum, largerSum;
    if (sum1 < sum2) {
        smaller = nums1;
        larger = nums2;
        smallerSum = sum1;
        largerSum = sum2;
    } else {
        smaller = nums2;
        larger = nums1;
        smallerSum = sum2;
        largerSum = sum1;
    }
    
    const diff = largerSum - smallerSum;
    
    // Calculate potential gains for each operation
    const gains = [];
    
    // Increase elements in smaller array
    for (let num of smaller) {
        gains.push(6 - num);
    }
    
    // Decrease elements in larger array
    for (let num of larger) {
        gains.push(num - 1);
    }
    
    // Sort gains in descending order
    gains.sort((a, b) => b - a);
    
    let operations = 0;
    let currentDiff = diff;
    
    for (let gain of gains) {
        if (currentDiff <= 0) break;
        currentDiff -= gain;
        operations++;
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n + m)
空间复杂度O(1)

其中 n 和 m 分别是 nums1 和 nums2 的长度。空间复杂度为常数级别，因为我们只使用了固定大小的数组来统计差值变化量。

相关题目