題目資訊

題目編號: 2918
題目連結: Minimum Equal Sum of Two Arrays After Replacing Zeros
主題: Array, Greedy

題目敘述

你被給予兩個由正整數組成的陣列 nums1 和 nums2。

你必須將這兩個陣列中的所有 0 替換為嚴格的正整數，使得兩個陣列的元素總和變得相等。

返回可以獲得的最小相等總和，或者如果不可能，則返回 -1。

範例 1:

輸入: nums1 = [3,2,0,1,0], nums2 = [6,5,0]
輸出: 12
解釋: 我們可以以下列方式替換 0：

將 nums1 中的兩個 0 替換為數值 2 和 4。結果陣列為 nums1 = [3,2,2,1,4]。
將 nums2 中的 0 替換為數值 1。結果陣列為 nums2 = [6,5,1]。
兩個陣列的總和都是 12。可以證明這是我們可以獲得的最小總和。

範例 2:

輸入: nums1 = [2,0,2,0], nums2 = [1,4]
輸出: -1
解釋: 不可能使兩個陣列的總和相等。

約束條件:

$1 \leq \text{nums1.length, nums2.length} \leq 10^5$
$0 \leq \text{nums1}[i], \text{nums2}[i] \leq 10^6$

直覺

這個問題涉及如何平衡兩個陣列 nums1 和 nums2 的和，透過將所有的零替換為嚴格正的整數。我們的目標是達到兩個陣列的和相等，並且使得這個和的總值儘可能的小。挑戰來源於這些零，它們提供了調整和的靈活性，但也使得確定最小相等和變得複雜。

解法

為了實現這個目標，我們需要考慮以下步驟：

計算初始和：首先，計算 nums1 和 nums2 中元素的和。這些初始和分別記作 sum1 和 sum2，它們將幫助我們了解兩個陣列之間的差距。
計數零的數量：確定每個陣列中的零的數量，分別記作 zeroCount1 和 zeroCount2。這些計數很重要，因為它們代表了我們在用正整數替換零時操作和的自由度。
檢查簡單情況：
- 如果兩個陣列都不含零且和已經相等，問題即得到解答，返回 sum1（或 sum2，因為它們相等）。
- 如果一個陣列沒有零且和之間的差距大到另一個陣列的零數不足以使和相等時，問題是無法解決的，返回 -1。這種情況出現在 sum1 < sum2 + zeroCount2 且 zeroCount1 == 0 或相反的情況。
確定最大可能貢獻：當存在零時，它們可以被替換為正值以潛在達到和相等。策略是在較小和的陣列中最大化地利用這些零來平衡兩個陣列的和。潛在的新和可以是 sum1 + zeroCount1 或 sum2 + zeroCount2，我們取這其中的最大值，確保返回經過調整後最低可能的相等和。
返回結果：使用上述邏輯，解決方案在於確保最終的和是等值且在給定限制和零數替換條件下盡可能小。

這個結構化方法確保問題是在指定限制和極端案例下得到解決的。

程式碼

C++

class Solution {
public:
    long long minSum(vector<int>& nums1, vector<int>& nums2) {
        // 計算 nums1 和 nums2 中所有元素的總和
        long long sum1 = accumulate(nums1.begin(), nums1.end(), 0LL);
        long long sum2 = accumulate(nums2.begin(), nums2.end(), 0LL);

        // 計算 nums1 和 nums2 中 0 的個數
        int zeroCount1 = count(nums1.begin(), nums1.end(), 0);
        int zeroCount2 = count(nums2.begin(), nums2.end(), 0);

        // 如果沒有 0 且總和相等，返回總和；否則返回 -1
        if (zeroCount1 == 0 && zeroCount2 == 0) {
            return sum1 == sum2 ? sum1 : -1;
        }

        // 當存在 0 時，檢查是否不可能使總和相等
        if ((zeroCount1 == 0 && sum1 < sum2 + zeroCount2) ||
            (zeroCount2 == 0 && sum2 < sum1 + zeroCount1)) {
            return -1;
        }

        // 通過用正整數替換 0，返回可以得到的最大可能總和
        return max(sum1 + zeroCount1, sum2 + zeroCount2);
    }
};

Python

class Solution:
    def minSum(self, nums1, nums2):
        # 計算 nums1 和 nums2 中元素的總和
        sum1 = sum(nums1)
        sum2 = sum(nums2)

        # 統計 nums1 和 nums2 中零的數量
        zeroCount1 = nums1.count(0)
        zeroCount2 = nums2.count(0)

        # 如果沒有零且總和相等，返回總和；否則返回 -1
        if zeroCount1 == 0 and zeroCount2 == 0:
            return sum1 if sum1 == sum2 else -1

        # 如果存在零且無法使總和相等，返回 -1
        if (zeroCount1 == 0 and sum1 < sum2 + zeroCount2) or (zeroCount2 == 0 and sum2 < sum1 + zeroCount1):
            return -1

        # 返回通過用正整數替換零能得到的最大可能總和
        return max(sum1 + zeroCount1, sum2 + zeroCount2)

複雜度分析

時間複雜度: $O(n)$
時間複雜度由操作 accumulate 和 count 決定，這兩個操作各自遍歷整個數組一次。給定兩個長度分別為 $n_1$ 和 $n_2$ 的數組 nums1 和 nums2，所需的時間為 $O(n_1) + O(n_2)$，簡化為 $O(n)$，其中 $n = n_1 + n_2$。
空間複雜度: $O(1)$
空間複雜度為 $O(1)$，因為無論輸入大小如何，算法僅使用恆定數量的額外空間。它只需要固定數量的變數來存儲和計算和零的計數。

CS Note
En

Leetcode 2918. Minimum Equal Sum of Two Arrays After Replacing Zeros

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析