Medium

题目描述

给你两个由正整数组成的数组 nums1 和 nums2。

你必须将两个数组中的所有 0 替换为严格正整数，使得两个数组元素的和相等。

返回你能获得的最小相等和，如果不可能则返回 -1。

示例 1：

输入：nums1 = [3,2,0,1,0], nums2 = [6,5,0]
输出：12
解释：我们可以按以下方式替换 0：
- 将 nums1 中的两个 0 替换为值 2 和 4。结果数组为 nums1 = [3,2,2,1,4]。
- 将 nums2 中的 0 替换为值 1。结果数组为 nums2 = [6,5,1]。
两个数组的和都等于 12。可以证明这是我们能获得的最小和。

示例 2：

输入：nums1 = [2,0,2,0], nums2 = [1,4]
输出：-1
解释：不可能使两个数组的和相等。

约束条件：

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

提示：

  • 考虑将两个数组中的所有 0 都替换为 1，如果和较小的数组中没有 0，答案将是 -1。
  • 否则，如何更新其中一个 1 的值来使两个数组的和相等？

解题思路

这道题需要我们找到替换零后两数组的最小相等和。核心思路是贪心算法：

  1. 初始计算：首先计算两个数组的非零元素和，以及每个数组中零的个数。

  2. 最小可能和：每个零至少要替换为1，所以每个数组的最小可能和等于非零元素和加上零的个数。

  3. 可行性判断：

    • 如果某个数组没有零，它的和是固定的
    • 如果两个数组都没有零且和不相等，返回-1
    • 如果一个数组没有零，另一个有零，检查是否能通过增加零的值来达到相等

  4. 最优解计算：

    • 如果两个数组都有零，最终答案是两个最小可能和的较大值
    • 如果只有一个数组有零，需要检查是否能调整到另一个数组的和

  5. 实现细节：使用贪心策略，优先将零替换为1，然后根据需要增加某些位置的值来平衡两个数组的和。

代码实现

class Solution {
public:
    long long minSum(vector<int>& nums1, vector<int>& nums2) {
        long long sum1 = 0, sum2 = 0;
        int zeros1 = 0, zeros2 = 0;
        
        for (int num : nums1) {
            sum1 += num;
            if (num == 0) zeros1++;
        }
        
        for (int num : nums2) {
            sum2 += num;
            if (num == 0) zeros2++;
        }
        
        long long minSum1 = sum1 + zeros1;
        long long minSum2 = sum2 + zeros2;
        
        if (zeros1 == 0 && zeros2 == 0) {
            return sum1 == sum2 ? sum1 : -1;
        }
        
        if (zeros1 == 0) {
            return sum1 >= minSum2 ? sum1 : -1;
        }
        
        if (zeros2 == 0) {
            return sum2 >= minSum1 ? sum2 : -1;
        }
        
        return max(minSum1, minSum2);
    }
};

class Solution:
    def minSum(self, nums1: List[int], nums2: List[int]) -> int:
        sum1 = sum(nums1)
        sum2 = sum(nums2)
        zeros1 = nums1.count(0)
        zeros2 = nums2.count(0)
        
        min_sum1 = sum1 + zeros1
        min_sum2 = sum2 + zeros2
        
        if zeros1 == 0 and zeros2 == 0:
            return sum1 if sum1 == sum2 else -1
        
        if zeros1 == 0:
            return sum1 if sum1 >= min_sum2 else -1
        
        if zeros2 == 0:
            return sum2 if sum2 >= min_sum1 else -1
        
        return max(min_sum1, min_sum2)

public class Solution {
    public long MinSum(int[] nums1, int[] nums2) {
        long sum1 = 0, sum2 = 0;
        int zeros1 = 0, zeros2 = 0;
        
        foreach (int num in nums1) {
            sum1 += num;
            if (num == 0) zeros1++;
        }
        
        foreach (int num in nums2) {
            sum2 += num;
            if (num == 0) zeros2++;
        }
        
        long minSum1 = sum1 + zeros1;
        long minSum2 = sum2 + zeros2;
        
        if (zeros1 == 0 && zeros2 == 0) {
            return sum1 == sum2 ? sum1 : -1;
        }
        
        if (zeros1 == 0) {
            return sum1 >= minSum2 ? sum1 : -1;
        }
        
        if (zeros2 == 0) {
            return sum2 >= minSum1 ? sum2 : -1;
        }
        
        return Math.Max(minSum1, minSum2);
    }
}

var minSum = function(nums1, nums2) {
    let sum1 = 0, zeros1 = 0;
    let sum2 = 0, zeros2 = 0;
    
    for (let num of nums1) {
        if (num === 0) {
            zeros1++;
            sum1 += 1;
        } else {
            sum1 += num;
        }
    }
    
    for (let num of nums2) {
        if (num === 0) {
            zeros2++;
            sum2 += 1;
        } else {
            sum2 += num;
        }
    }
    
    if (zeros1 === 0 && zeros2 === 0) {
        return sum1 === sum2 ? sum1 : -1;
    }
    
    if (zeros1 === 0) {
        return sum1 >= sum2 ? sum1 : -1;
    }
    
    if (zeros2 === 0) {
        return sum2 >= sum1 ? sum2 : -1;
    }
    
    return Math.max(sum1, sum2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)其中 n 和 m 分别是 nums1 和 nums2 的长度，需要遍历两个数组各一次
空间复杂度O(1)只使用了常数级别的额外空间