当前位置：首页 > news >正文

力扣热题——数组的最小相等和

news 2025/7/4 19:50:43

题目链接：2918. 数组的最小相等和 - 力扣（LeetCode）

题目描述

解法一：

解决思路

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

总结

题目链接：2918. 数组的最小相等和 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

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

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

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

示例 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

解法一：

解决思路

计算非零元素和零的数量
- 遍历两个数组，分别计算每个数组中非零元素的总和（sum1 和 sum2）以及零的数量（zero1 和 zero2）。
处理特殊情况
- 情况1：两个数组都没有零
  - 直接比较两个数组的非零总和是否相等。若相等，返回该总和；否则返回 -1。
- 情况2：其中一个数组没有零
  - 例如，nums1 无零，则 nums2 的总和必须调整到与 sum1 相等。此时需要满足：
    - sum1 ≥ sum2 + zero2（因为 nums2 的最小总和为 sum2 + zero2，每个零替换为1）。
  - 若满足条件，返回 sum1；否则返回 -1。
处理一般情况（两个数组都有零）
- 计算每个数组的最小可能总和：
  - nums1 的最小总和：sum1 + zero1（每个零替换为1）。
  - nums2 的最小总和：sum2 + zero2（每个零替换为1）。
- 最终的总和必须至少是这两个值的较大者，因为较小的总和无法通过调整零的替换值来匹配较大的总和。

Java写法：

public class Solution {public long minSum(int[] nums1, int[] nums2) {long sum1 = 0;int zero1 = 0;for (int num : nums1) {if (num == 0) {zero1++;} else {sum1 += num;}}long sum2 = 0;int zero2 = 0;for (int num : nums2) {if (num == 0) {zero2++;} else {sum2 += num;}}// 处理两个数组都没有0的情况if (zero1 == 0 && zero2 == 0) {return sum1 == sum2 ? sum1 : -1;}// 处理nums1没有0的情况if (zero1 == 0) {// sum1必须 >= sum2 + zero2，因为sum2的最小总和是sum2 + zero2if (sum1 >= sum2 + zero2) {return sum1;} else {return -1;}}// 处理nums2没有0的情况if (zero2 == 0) {if (sum2 >= sum1 + zero1) {return sum2;} else {return -1;}}// 其他情况，计算两者的最小可能总和的最大值long s1 = sum1 + zero1;long s2 = sum2 + zero2;return Math.max(s1, s2);}
}

C++写法：

#include <vector>
#include <algorithm> // 用于max函数using namespace std;class Solution {
public:long long minSum(vector<int>& nums1, vector<int>& nums2) {long long sum1 = 0, sum2 = 0;int zero1 = 0, zero2 = 0;// 计算nums1的非零总和和零的数量for (int num : nums1) {if (num == 0) zero1++;else sum1 += num;}// 计算nums2的非零总和和零的数量for (int num : nums2) {if (num == 0) zero2++;else sum2 += num;}// 情况1：两个数组都没有零if (zero1 == 0 && zero2 == 0) {return (sum1 == sum2) ? sum1 : -1;}// 情况2：nums1没有零，nums2必须调整到sum1的总和if (zero1 == 0) {if (sum1 >= sum2 + zero2) return sum1;else return -1;}// 情况3：nums2没有零，nums1必须调整到sum2的总和if (zero2 == 0) {if (sum2 >= sum1 + zero1) return sum2;else return -1;}// 情况4：两个数组都有零，取最小总和的较大者long long minSum1 = sum1 + zero1;long long minSum2 = sum2 + zero2;return max(minSum1, minSum2);}
};