給你兩個由正整數和?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
分析:不難想到,將數組中的所有 0 變為 1 能夠使該數組所有元素的和最小。令 sum1, sum2 分別為 nums1,nums2 的不為零元素之和,cnt1,cnt2 為兩個數組為 0 的元素數量,則兩個數組可以達到的最小和為:sum1+cnt1,sum2+cnt2。
當兩個數組至少都存在 1 個 0 時,一定存在答案,且答案為兩個最小和的較大值。
當某個數組中不存在 0 時,如果另一個數組可達的最小和大于此數組的和,由于沒有辦法使此數組的和變大使得兩個數組的和相等,返回-1.
long long minSum(int* nums1, int nums1Size, int* nums2, int nums2Size) {long long sum1 = 0, sum2 = 0;int zero1 = 0, zero2 = 0;for (int i = 0; i < nums1Size; i++) {sum1 += nums1[i];if (nums1[i] == 0) {sum1 += 1;zero1++;}}for (int i = 0; i < nums2Size; i++) {sum2 += nums2[i];if (nums2[i] == 0) {sum2 += 1;zero2++;}}if ((zero1 == 0 && sum2 > sum1) || (zero2 == 0 && sum1 > sum2)) {return -1;}return sum1 > sum2 ? sum1 : sum2;
}