题目描述
给你两个由正整数和 0
组成的数组 nums1
和 nums2
。
你必须将两个数组中的 所有 0
替换为 严格 正整数,并且满足两个数组中所有元素的和 相等。
返回 最小 相等和,如果无法使两数组相等,则返回 -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。可以证明这是可以获得的最小相等和。
输入:nums1 = [2,0,2,0], nums2 = [1,4]
输出:-1
解释:无法使两个数组的和相等。
限制
1 <= nums1.length, nums2.length <= 10^5
0 <= nums1[i], nums2[i] <= 10^6
算法
(思维题) $O(n)$
- 分别求出两个数组的总和和 $0$ 的个数,$tot1$、$z1$ 和 $tot2$、$z2$。
- 如果 $z1$ 和 $z2$ 都为 $0$,则判断 $tot1$ 是否等于 $tot2$ 并返回。
- 如果只有 $z1$ 为 $0$,则判断 $tot2 + z2$ 是否小于等于 $tot1$。当第二个数组中所有的 $0$ 都变为 $1$ 时,如果不会超过 $tot1$,则证明第二个数组的总和最终可以变为 $tot1$。
- 如果只有 $z2$ 为 $0$,则同理判断。
- 如果都不为 $0$,则返回 $tot1 + z1$ 与 $tot2 + z2$ 的最小值。
时间复杂度
- 两个数组分别遍历一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
#define LL long long
class Solution {
public:
LL minSum(vector<int>& nums1, vector<int>& nums2) {
LL tot1 = 0, tot2 = 0;
int z1 = 0, z2 = 0;
for (int x : nums1) {
if (x == 0)
++z1;
tot1 += x;
}
for (int x : nums2) {
if (x == 0)
++z2;
tot2 += x;
}
if (z1 == 0 && z2 == 0)
return tot1 == tot2 ? tot1 : -1;
if (z1 == 0)
return tot2 + z2 <= tot1 ? tot1 : -1;
if (z2 == 0)
return tot1 + z1 <= tot2 ? tot2 : -1;
return max(tot1 + z1, tot2 + z2);
}
};