88. Merge Sorted Array

題目 / Problem

中文： 給定兩個按 非遞減順序 排序的整數陣列 nums1 和 nums2，以及兩個整數 m 和 n，分別代表 nums1 與 nums2 中的元素個數。

請將 nums2 合併 到 nums1 中，使合併後的陣列同樣為非遞減排序。

最終結果不需 return，而是必須 原地儲存在 nums1 中。為此，nums1 的長度為 m + n：前 m 個為真正要合併的元素，後 n 個預留為 0（應忽略）。nums2 的長度為 n。

English: You are given two integer arrays nums1 and nums2, both sorted in non-decreasing order, and two integers m and n giving the number of real elements in each.

Merge nums2 into nums1 so the combined array is also sorted in non-decreasing order. The result must be stored in-place inside nums1 (no return value). nums1 has length m + n: the first m slots hold the real values, and the last n slots are filler zeros that should be overwritten.

Constraints / 限制： - nums1.length == m + n - nums2.length == n - 0 <= m, n <= 200 - 1 <= m + n <= 200 - -10^9 <= nums1[i], nums2[j] <= 10^9

Example / 範例：

Input:  nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: nums1 = [1,2,2,3,5,6]

名詞解釋 / Glossary

• 原地修改 / in-place modification — 直接在輸入陣列上寫入結果，不另外配置一個新陣列。題目要求我們把答案寫回 nums1，額外空間應降到 O(1)。 / Writing the answer directly into the input array instead of allocating a new one. The problem demands we store the merged result inside nums1, aiming for O(1) extra space.
• 雙指針 / two pointers — 用兩個索引變數各自指向不同陣列（或同一陣列的不同位置），每一步根據比較結果移動其中之一。這是合併有序序列的標準技巧。 / Using two index variables that each scan a different array (or different positions in the same array), advancing one of them at each step based on a comparison. This is the canonical technique for merging sorted sequences.
• 從後往前填 / fill from the back — 一般合併會從左到右寫，但那會覆蓋 nums1 尚未讀取的資料。若改從 nums1 的 最後一格往前 寫，因為尾端是空的 0，永遠不會踩到還沒處理的資料。 / Normally we'd merge left-to-right, but that would overwrite values in nums1 we haven't read yet. Writing from the back of nums1 toward the front works because the tail is filler zeros — we never clobber unread data.
• 不變量 / invariant — 在演算法執行過程中恆為真的性質。這題的不變量是：寫入指針 k 右邊的所有格子都已經放好最終的最大元素（且已排序）。 / A property that stays true throughout the algorithm's execution. Here the invariant is: everything to the right of the write pointer k is already finalized and holds the largest merged values in sorted order.
• 非遞減 / non-decreasing — 相鄰元素滿足 a[i] <= a[i+1]，允許相等（所以允許重複值）。 / Adjacent elements satisfy a[i] <= a[i+1]; equal values are allowed (duplicates permitted).

思路

最直覺的暴力解是：把 nums2 的 n 個元素接在 nums1 前 m 個元素後面，再對整個 nums1 做一次排序，複雜度 O((m+n) log(m+n))。這能過，但浪費了「兩個陣列本來就已經排序好」這個重要資訊。更好的作法是雙指針合併：同時掃兩個陣列，每次挑出當前較小的那個放到結果中，這是歸併排序的合併步驟，時間 O(m+n)。但若從前往後寫，新寫入會覆蓋 nums1 還沒比較過的值，因此需要另開一個輔助陣列，多花 O(m+n) 空間。關鍵的洞見是：nums1 尾端那 n 個 0 其實是「免費的空位」，我們可以反過來 從後往前 填，每次挑兩個陣列末端剩餘元素中較大的那個放到 nums1 的最後一個空格。由於寫入位置 k 總是在「已讀」的位置之後（寫指針永遠跑在讀指針前面），絕不會覆蓋尚未處理的資料，完美地做到 O(m+n) 時間 + O(1) 空間的原地合併。

The brute-force approach is to copy nums2's n elements into the tail of nums1 and then sort the whole thing, which costs O((m+n) log(m+n)) — it works but throws away the fact that both inputs are already sorted. A better approach is the two-pointer merge from mergesort: walk both arrays in parallel, picking the smaller current element each step, for O(m+n) time. Done left-to-right, though, we'd overwrite entries of nums1 we haven't read yet, forcing a temporary buffer of size O(m+n). The key insight is that the trailing n zeros in nums1 give us free scratch space at the back, so we merge from right to left: at each step, compare the last unprocessed element of nums1 with the last unprocessed element of nums2, place the larger one at position k (the rightmost unfilled slot), and move pointers leftward. Because the write pointer k is always at or ahead of the read pointer into nums1, we never clobber data we still need — giving an O(m+n) time, O(1) space in-place merge.

逐步走查 / Walkthrough

以 nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 為例。

令 i = m-1 = 2（指向 nums1 最後一個真實元素），j = n-1 = 2（指向 nums2 最後一個元素），k = m+n-1 = 5（寫入指針，指向 nums1 最末尾）。每步比較 nums1[i] 與 nums2[j]，把較大的放到 nums1[k]，然後對應指針左移、k 也左移。

當 j < 0 時，nums2 已全部放完，而 nums1 前面尚未處理的部分本來就已經排序並停留在正確位置，因此結束即可。若反過來是 i < 0 先發生（nums1 的真實元素先用完），就必須把 nums2 剩下的元素繼續複製到前面。

When j < 0, nums2 is exhausted and any remaining nums1 elements at the front are already in their final sorted positions — we're done. If instead i < 0 happens first, we must keep copying the leftover nums2 values into the front of nums1.

Solution — C

// 演算法：雙指針從後往前合併。i 指 nums1 尾端、j 指 nums2 尾端、k 為寫入位置。
// Algorithm: two-pointer merge from the back. i walks nums1's real tail, j walks
// nums2's tail, k is the write slot. Each step places max(nums1[i], nums2[j]) at k.
// 時間 O(m+n)，空間 O(1)。 / O(m+n) time, O(1) space.

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    // nums1Size / nums2Size 參數用不到；LeetCode 的 C 介面硬性要求帶上陣列長度。
    // nums1Size / nums2Size are unused; LeetCode's C signature mandates passing lengths.
    (void)nums1Size;  // 抑制未使用參數的編譯警告 / silence "unused parameter" warnings
    (void)nums2Size;  // 同上 / same as above

    int i = m - 1;         // i 指向 nums1 目前最後一個真實元素 / index of last real nums1 element
    int j = n - 1;         // j 指向 nums2 目前最後一個元素 / index of last nums2 element
    int k = m + n - 1;     // k 指向 nums1 的最後一格（寫入位置）/ write position at tail of nums1

    // 只要 nums2 還有元素就要繼續合併；nums1 側若先用完由下方補抄處理。
    // Loop while nums2 still has elements; leftover nums1 prefix needs no action
    // because it is already sorted and sits in its final place.
    while (j >= 0) {
        // 若 nums1 真實元素已耗盡，直接把剩下的 nums2 複製過去。
        // If nums1's real elements are exhausted, just drain nums2 into the front.
        if (i < 0) {
            nums1[k] = nums2[j];  // 把 nums2[j] 寫入 nums1[k] / copy nums2[j] into slot k
            j--;                  // nums2 指針左移 / move nums2 pointer left
            k--;                  // 寫入指針左移 / move write pointer left
            continue;             // 跳回 while 檢查 / back to loop condition
        }

        // 兩邊都還有元素：取較大者放到尾部（這樣剩下的都 <= 它，仍是合法的非遞減）。
        // Both sides still have elements: place the larger one at slot k. Everything
        // left to place is <= it, preserving non-decreasing order from k rightward.
        if (nums1[i] > nums2[j]) {
            nums1[k] = nums1[i];  // nums1[i] 較大，放到 k / nums1[i] is larger, write it to k
            i--;                  // nums1 指針左移 / move nums1 read pointer left
        } else {
            // 相等時取 nums2[j] 也可，結果仍為非遞減排序。
            // On tie we pick nums2[j]; result is still non-decreasing either way.
            nums1[k] = nums2[j];  // nums2[j] 較大或相等，放到 k / nums2[j] wins (or tied), write to k
            j--;                  // nums2 指針左移 / move nums2 pointer left
        }
        k--;  // 無論走哪條分支，寫入位置都要左移一格 / write slot shifts left either way
    }
    // 迴圈結束時 j < 0：nums2 全部處理完畢，nums1 前段本來就排好，直接結束即可。
    // When the loop exits, j < 0: nums2 is fully merged and nums1's front prefix
    // was already sorted in place — no more work needed.
}

Solution — C++

// 演算法同 C 版：雙指針從後往前合併 nums1 與 nums2，原地完成。
// Same algorithm as the C version: merge from the back with two pointers, in-place.
// 時間 O(m+n)，空間 O(1)。 / O(m+n) time, O(1) space.

class Solution {
public:
    // vector<int>& 是「對 int 向量的參考」：不會複製，直接改呼叫者傳入的陣列。
    // vector<int>& is a reference to an int vector: no copy, we mutate the caller's array.
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;        // nums1 最後一個真實元素的索引 / index of last real nums1 element
        int j = n - 1;        // nums2 最後一個元素的索引 / index of last nums2 element
        int k = m + n - 1;    // nums1 寫入位置，從最尾端開始 / write slot, starting at nums1's tail

        // while 條件合併兩個指針：任何一邊還有東西、就繼續。
        // Loop while either side still has unplaced elements.
        while (i >= 0 && j >= 0) {
            // 三元運算子 cond ? a : b：若 cond 為真取 a，否則取 b。
            // Ternary operator cond ? a : b: pick a if cond is true, else b.
            // 取兩邊末端較大者放到 nums1[k]，並把對應讀指針往左推一格。
            // Place the larger tail value at nums1[k] and step that read pointer left.
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];  // 等同寫 nums1[k]=nums1[i]; k--; i--; / shorthand for three statements
            } else {
                nums1[k--] = nums2[j--];  // 相等時走這條分支也沒問題 / tie-breaking via this branch is safe
            }
        }

        // 若 nums1 先耗盡 (i < 0)，剩下的 nums2 還需要倒進 nums1 前面。
        // If nums1 was exhausted first (i < 0), drain remaining nums2 into the front.
        // 若 nums2 先耗盡 (j < 0)，nums1 前段已經在正確位置，不必動。
        // If nums2 was exhausted first (j < 0), nums1's prefix is already in place — skip.
        while (j >= 0) {
            nums1[k--] = nums2[j--];  // 繼續由後往前把 nums2 剩餘值複製過去 / keep copying leftover nums2 back-to-front
        }
        // 此處無 return：函式回傳型別 void，且題目要求原地修改 nums1。
        // No return: the function is void and the problem requires in-place mutation of nums1.
    }
};

複雜度 / Complexity

• Time: O(m + n) — 每次迴圈迭代都會讓 i、j、或 k 之一前進（向左）一格，所以總共最多 m + n 次迭代，每次做 O(1) 的比較與賦值。 / Each loop iteration advances one of i, j, or k leftward, so we run at most m + n iterations, each doing O(1) work (one compare, one assignment).
• Space: O(1) — 只用了三個整數索引 i、j、k，沒有額外配置任何陣列或資料結構；所有寫入都發生在原 nums1 內部。 / We use only three integer indices (i, j, k) and no auxiliary arrays — all writes happen inside the original nums1.

Pitfalls & Edge Cases

• 從前往後合併會覆蓋資料 / Front-to-back merge clobbers data — 若從 k = 0 往右寫，會把 nums1 還沒比較的元素直接覆蓋掉。從後往前寫利用尾端空位，避免這個陷阱。 / Writing from k = 0 rightward overwrites unread nums1 entries. Writing from the back uses the trailing zeros as free scratch space, dodging the issue.
• n == 0（nums2 為空） / n == 0 (empty nums2) — 此時 j = -1，主迴圈一次都不會進入，nums1 保持原樣，正確。 / Here j starts at -1, the main loop body is skipped entirely, nums1 is left untouched — correct behavior.
• m == 0（nums1 無真實元素） / m == 0 (nums1 has no real elements) — i = -1，程式會走「補抄 nums2」的分支，把 nums2 完整複製到 nums1。 / i starts at -1, so control flows into the "drain nums2" branch and copies it wholesale into nums1.
• 忘記處理 nums2 剩餘 / Forgetting to drain remaining nums2 — 若只用單一 while (i >= 0 && j >= 0) 而不補一段處理 j >= 0，當 nums1 先用完時，nums2 前段較小的元素會留在原地沒被搬進去，答案錯誤。兩份解答都明確處理了此狀況。 / Using a single while (i >= 0 && j >= 0) loop without a follow-up drain leaves the front of nums2 unmerged when nums1 runs out first, producing a wrong answer. Both solutions explicitly handle the drain.
• 不需處理 nums1 剩餘 / No need to drain leftover nums1 — 如果 nums2 先用完，nums1 前段早已排序且就在正確位置，多寫反而可能混亂。 / If nums2 finishes first, the leftover prefix of nums1 is already sorted in place — copying it would be redundant (and, if done wrong, buggy).
• 整數大小 / Integer range — 元素值域為 [-10^9, 10^9]，32-bit int 可容納，不必用 long long。 / Values fit within [-10^9, 10^9], so a 32-bit int is sufficient — no need for long long.
• 相等元素 / Equal values — 題目要求非遞減（允許相等），所以 nums1[i] == nums2[j] 時選任一邊放入皆可；程式用 > 比較，相等時走 nums2 分支，結果仍正確。 / Non-decreasing allows duplicates, so ties can go to either side. The code uses >, sending ties down the nums2 branch — still correct.