Leetcode2918. 数组的最小相等和

Every day a Leetcode

题目来源：2918. 数组的最小相等和

解法1：贪心

设数组 nums1 的元素总和为 sum1，其中 0 的个数为 countZero1；数组 nums2 的元素总和为 sum2，其中 0 的个数为 countZero2。

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

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

基于贪心的思想，把所有的 0 改成 1，所有元素的和为最小。于是，数组 nums1 的最小和为 sum1 + countZero1，数组 nums2 的最小和为 sum2 + countZero2。

分类讨论：

• 如果 sum1 < sum2 + countZero2 && countZero1 == 0，说明无法将数组 nums1 修改到和修改后的数组 nums2 的和相等，返回 -1。
• 如果 sum2 < sum1 + countZero1 && countZero2 == 0，说明无法将数组 nums2 修改到和修改后的数组 nums1 的和相等，返回 -1。
• 其他情况，都能得到最小相等和。最小相等和为两个最小和的较大值，即 max(sum1 + countZero1, sum2 + countZero2)。

代码：

/*
 * @lc app=leetcode.cn id=2918 lang=cpp
 *
 * [2918] 数组的最小相等和
 */

// @lc code=start
class Solution
{
public:
    long long minSum(vector<int> &nums1, vector<int> &nums2)
    {
        long long sum1 = 0, sum2 = 0;
        int countZero1 = 0, countZero2 = 0;
        for (const int num : nums1)
        {
            if (num)
                sum1 += num;
            else
                countZero1++;
        }
        for (const int num : nums2)
        {
            if (num)
                sum2 += num;
            else
                countZero2++;
        }
        if (sum1 < sum2 + countZero2 && countZero1 == 0)
            return -1;
        if (sum2 < sum1 + countZero1 && countZero2 == 0)
            return -1;
        return max(sum1 + countZero1, sum2 + countZero2);
    }
};
// @lc code=end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

结果：

复杂度分析：

时间复杂度：O(n+m)，其中 n 为数组 nums1 的长度，m 为数组 nums2 的长度。

空间复杂度：O(1)。