88. Merge Sorted Array

📘 題目敘述

給定兩個整數陣列 nums1 與 nums2，它們都已經按照非遞減順序排序。

• nums1 的長度為 m + n，前 m 個元素是有效資料，最後 n 個位置是 0（只是佔位用）
• nums2 的長度為 n，包含 n 個有效元素

請你將 nums2 合併進 nums1，使得合併後的 nums1 仍然是排序好的結果。

題目要求：不要回傳任何值，直接修改 nums1。

條件限制

• nums1.length == m + n
• nums2.length == n
• 0 ≤ m, n ≤ 200
• 1 ≤ m + n ≤ 200
• -10^9 ≤ nums1[i], nums2[j] ≤ 10^9

🧠 解題思路

我的想法是用「兩個指標」去合併兩個已排序的陣列，做法很像 merge sort 的合併步驟。

因為：

• nums1 的前 m 個是有效排序資料
• nums2 的 n 個也都是排序資料

所以我可以：

1. 用 pos1 指向 nums1 的有效區間開頭
2. 用 pos2 指向 nums2 的開頭
3. 每次比較 nums1[pos1] 和 nums2[pos2]
4. 把比較小的那個放進一個新的陣列 nums
5. 對應的指標往前移
6. 最後把剩下的元素全部補進 nums

等 nums 變成完整的合併結果後，再把它寫回 nums1。

所有變數

• m：nums1 中有效元素的數量（只看前 m 個）
• n：nums2 的元素數量
• nums：我額外開的一個暫存陣列，用來存合併後的排序結果
• pos1：掃描 nums1 有效區間的指標（範圍 0 ~ m-1）
• pos2：掃描 nums2 的指標（範圍 0 ~ n-1）

🪜 主要流程步驟

第一步：同時掃描兩個陣列，逐個放入較小值

當 pos1 < m 且 pos2 < n 時代表：

• nums1 還有有效元素可以比較
• nums2 也還有元素可以比較

我每次都做同一件事：

• 若 nums1[pos1] < nums2[pos2] → 把 nums1[pos1] 放進 nums，然後 pos1++
• 否則（代表 nums2[pos2] 比較小或相等） → 把 nums2[pos2] 放進 nums，然後 pos2++

這樣可以確保 nums 一直保持排序。

第二步：把剩下沒放完的那一邊全部補上

當第一段 while 結束時，代表：

• 其中一個陣列已經用完了
• 另一個陣列可能還有剩下的元素

因為剩下的元素本來就已經排序好，所以我直接整段補進 nums：

• 如果 pos1 < m → 把 nums1 剩下的有效元素全部 push 進去
• 如果 pos2 < n → 把 nums2 剩下的元素全部 push 進去

第三步：把合併結果寫回 nums1

最後題目要求直接修改 nums1，所以我做兩件事：

1. 先把 nums1 的長度調整成 m + n，用 nums1.resize(m + n) 確保大小正確
2. 再把 nums 中的每個元素依序寫回 nums1[i]

這樣合併後的結果就完整存在 nums1 裡面。

💡 整體邏輯總結

這題我的重點是：

• 因為兩個陣列都已經排序好
• 所以用兩個指標從頭往後掃描
• 每次選較小的放進新陣列
• 最後再把結果寫回 nums1

整體流程直觀，且能一次完成合併。

💻 程式碼實作

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> nums;
        int pos1 = 0, pos2 = 0;
        while (pos1 < m && pos2 < n) {
            if (nums1[pos1] < nums2[pos2]) {
                nums.push_back(nums1[pos1]);
                pos1++;
            } else {
                nums.push_back(nums2[pos2]);
                pos2++;
            }
        }
        while (pos1 < m) {
            nums.push_back(nums1[pos1]);
            pos1++;
        }
        while (pos2 < n) {
            nums.push_back(nums2[pos2]);
            pos2++;
        }
        nums1.resize(m + n);
        for (int i = 0; i < m + n; i++) {
            nums1[i] = nums[i];
        }
    }
};

🔗 題目連結

https://leetcode.com/problems/merge-sorted-array/