題目資訊

題目編號: 2570
題目連結: Merge Two 2D Arrays by Summing Values
主題: Array, Hash Table, Two Pointers

題目敘述

您被給予兩個 2D 整數數組 nums1 和 nums2。

$nums1[i] = [id_i, val_i]$ 表示具有 id $id_i$ 的數字的值等於 $val_i$。
$nums2[i] = [id_i, val_i]$ 表示具有 id $id_i$ 的數字的值等於 $val_i$。

每個數組包含唯一路徑，並按照 id 升序排序。

將兩個數組合併成一個數組，並按照 id 的升序排序，符合以下條件：

僅包含至少出現在兩個數組之一中的 id。
每個 id 只能包含一次，其值應為該 id 在兩個數組中的值之和。如果該 id 未出現在其中一個數組中，則假設其在該數組中的值為 $0$。

返回合併後的數組。返回的數組必須按照 id 的升序排序。

範例 1:

輸入: nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
輸出: [[1,6],[2,3],[3,2],[4,6]]
說明: 合併後的數組包含以下內容:
- id = 1，此 id 的值為 2 + 4 = 6。
- id = 2，此 id 的值為 3。
- id = 3，此 id 的值為 2。
- id = 4，此 id 的值為 5 + 1 = 6。

範例 2:

輸入: nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]
輸出: [[1,3],[2,4],[3,6],[4,3],[5,5]]
說明: 沒有共同的 id，所以我們只需將每個 id 及其值包含在合併後的列表中。

約束條件:

$1 \leq nums1.length, nums2.length \leq 200$
$nums1[i].length == nums2[j].length == 2$
$1 \leq id_i, val_i \leq 1000$
兩個數組都包含唯一的 id。
兩個數組按照 id 嚴格升序排列。

直覺

這個問題要求合併兩個獨立的二維陣列，每個陣列都包含 id-value 配對，使得合併後的陣列包含所有唯一的 id，以升序排列，並且對於在兩個陣列中都存在的 id 聚合其值。解決方案需要有效地考慮以下約束條件：每個陣列中的 id 是唯一的，並且兩個陣列都是預排序的，因此可以使用雙指針技術同時遍歷每個陣列。

解法

為了解決這個問題，我們實施了一個雙指針策略來同時導航兩個二維陣列。通過利用已排序陣列和唯一 id 的特性，我們可以通過以下步驟有效地將它們合併：

初始化: 定義一個空的結果陣列用於存儲合併後的 id 和值。初始化指標 idx1 和 idx2 用於追蹤 nums1 和 nums2 中的位置。
迭代合併: 使用一個循環來遍歷兩個陣列，直到所有元素都被處理完：
- 如果指標 idx1 到達了 nums1 的末端，則將 nums2 中剩餘的元素附加到結果中，因為 nums2 本身已排序。
- 相反地，如果指標 idx2 到達了 nums2 的末端，則將 nums1 中剩餘的元素附加到結果中，原因相同。
- 比較 idx1 和 idx2 所指向的當前 id。將較小的 id-value 配對附加到結果中，並推進相應的指標。
- 如果兩個 id 相同，計算它們值的和，將 id 和計算出的和附加到結果中，然後同時推進兩個指標。
完成: 一旦循環結束，結果將包含所有唯一 id 和其各自聚合後的值，並且以升序排列。

通過有效地運用這些步驟，該演算法實現了兩個陣列的最佳合併，保持順序並確保滿足問題描述中指定的所有條件。

程式碼

C++

class Solution {
public:
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
        vector<vector<int>> result; // 結果陣列用於儲存合併後的結果
        int len1 = nums1.size(), len2 = nums2.size();
        int idx1 = 0, idx2 = 0;
        
        // 當任一陣列中還有元素時，遍歷兩個陣列
        while (idx1 < len1 || idx2 < len2) {
            if (idx1 == len1) {
                // 若nums1已經遍歷完畢，從nums2中取出元素
                result.push_back(nums2[idx2++]);
            } else if (idx2 == len2) {
                // 若nums2已經遍歷完畢，從nums1中取出元素
                result.push_back(nums1[idx1++]);
            } else if (nums1[idx1][0] < nums2[idx2][0]) {
                // 若nums1中的當前id較小，取出此id-值對
                result.push_back(nums1[idx1++]);
            } else if (nums2[idx2][0] < nums1[idx1][0]) {
                // 若nums2中的當前id較小，取出此id-值對
                result.push_back(nums2[idx2++]);
            } else {
                // 若id相等，合併其值
                result.push_back(nums1[idx1++]);
                result.back()[1] += nums2[idx2++][1]; // 將值相加
            }
        }
        
        return result; // 返回合併後的陣列
    }
};

Python

class Solution:
    def mergeArrays(self, nums1, nums2):
        result = []  # 儲存合併結果的陣列
        len1 = len(nums1)
        len2 = len(nums2)
        idx1 = 0
        idx2 = 0
        
        # 當任一陣列中仍有元素時，遍歷兩個陣列
        while idx1 < len1 or idx2 < len2:
            if idx1 == len1:
                # 如果 nums1 用完了，從 nums2 取元素
                result.append(nums2[idx2])
                idx2 += 1
            elif idx2 == len2:
                # 如果 nums2 用完了，從 nums1 取元素
                result.append(nums1[idx1])
                idx1 += 1
            elif nums1[idx1][0] < nums2[idx2][0]:
                # 如果目前 nums1 的 id 較小，取出這個 id-值 配對
                result.append(nums1[idx1])
                idx1 += 1
            elif nums2[idx2][0] < nums1[idx1][0]:
                # 如果目前 nums2 的 id 較小，取出這個 id-值 配對
                result.append(nums2[idx2])
                idx2 += 1
            else:
                # 如果 id 相等，合併其值
                result.append(nums1[idx1])
                result[-1][1] += nums2[idx2][1]  # 合併值
                idx1 += 1
                idx2 += 1
        
        return result  # 返回合併後的陣列

複雜度分析

時間複雜度: 給定的演算法對 nums1 和 nums2 這兩個陣列各遍歷一次。nums1 或 nums2 中的每個元素都只被處理一次，因此時間複雜度為 $O(n + m)$，其中 $n$ 是 nums1 的長度，$m$ 是 nums2 的長度。
空間複雜度: 演算法所使用的空間與 nums1 或 nums2 中存在的唯一 id 的數量成正比。在最壞情況下，兩個陣列中的所有 id 都是唯一的，這意味著 result 陣列所需的空間將與 nums1 和 nums2 的長度之和成正比。因此，空間複雜度是 $O(n + m)$。

CS Note
En

Leetcode 2570. Merge Two 2D Arrays by Summing Values

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析