[LeetCode] 每日一题 2918. 数组的最小相等和（贪心算法）

题目描述

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

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

返回 最小 相等和 ，如果无法使两数组相等，则返回 -1 。

题目链接

https://leetcode.cn/problems/minimum-equal-sum-of-two-arrays-after-replacing-zeros

示例输入

示例 1

输入：nums1 = [3,2,0,1,0], nums2 = [6,5,0]
输出：12
解释：可以按下述方式替换数组中的 0 ：
- 用 2 和 4 替换 nums1 中的两个 0 。得到 nums1 = [3,2,2,1,4] 。
- 用 1 替换 nums2 中的一个 0 。得到 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，否则无法满足“严格正整数”的要求。所以我们可以先把两个数组中所有的 0 都假设成 1，算出这时候的总和 sum1 和 sum2。

之后，我们的目标就很明确了：把较小的一边通过替换更大的数来“补差值”，从而让两个数组的和相等。我们并不关心具体怎么替换，只要有替换的余地即可。

贪心关键点在于：

• 谁小谁补：如果 sum1 < sum2，我们就要看 sum1 对应数组是否还有 0 来补；

• 无 0 无法补：如果小的一边没有 0，那就无法补出差值，直接返回 -1；

• 其他情况都能补出一个合理的最小值，那就返回 max(sum1, sum2)。

代码实现

class Solution {
    public long minSum(int[] nums1, int[] nums2) {
        int count1 = 0, count2 = 0;
        long sum1 = 0, sum2 = 0;
        for (int num : nums1) {
            if (num == 0) {
                count1++;
                sum1++;
            } else {
                sum1 += num;
            }
        }
        for (int num : nums2) {
            if (num == 0) {
                count2++;
                sum2++;
            } else {
                sum2 += num;
            }
        }
        // 保证 sum1 是较大值
        if (sum1 < sum2) {
            long temp = sum1;
            sum1 = sum2;
            sum2 = temp;
            count2 = count1;
        }
        // 如果差值无法补齐
        if (sum1 != sum2 && count2 == 0) {
            return -1;
        }
        return sum1;
    }
}

复杂度分析

• 时间复杂度：

  • O(n + m)，其中 n 是 nums1 的长度，m 是 nums2 的长度，只需遍历两次

• 空间复杂度：

  • O(1)，只用常数级变量

总结

这题虽然看上去跟“替换”、“相等”相关，但本质上只需要一个局部最优的替换策略 —— 全部替换成最小正整数（即 1），就可以快速定位到两数组和之间的关系

整个过程就像是一个典型的“能补则补，不能补就退出”的贪心逻辑，在校招刷题中遇到类似“必须替换满足条件”的题，可以考虑从最小可行值出发👍

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。