88. Merge Sorted Array

题目描述：

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

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

最終，合併後的陣列不應由函數返回，而是存儲在陣列 nums1 中。為了應對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應合併的元素，後 n 個元素為 0，應忽略。nums2 中的元素也需要合併到 nums1 中。

Example:

• Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
• Output: [1,2,2,3,5,6]
• Explanation: 我們要合併的陣列是 [1,2,3] 和 [2,5,6]。合併的結果是 [1,2,2,3,5,6]，其中下劃線的元素來自 nums1。

解題思路:
這道題目是一道實作題，主要考驗讀者如何合併兩個排序好的陣列。題目要求將 nums2 合併到 nums1 中，並確保合併後的陣列依然是非遞減順序。這裡我們可以使用「雙指針」(Two Pointers)來跟蹤兩個陣列的位置。

因為 nums1 的末尾已經預留了足夠的空間來容納 nums2 的元素，所以我們可以從兩個陣列的末尾開始比較，將較大的元素填入 nums1 的最後位置。這樣可以避免覆蓋 nums1 中還未處理的元素。

如果 nums2 中還有剩餘的元素，那麼將它們直接拷貝到 nums1 的前面即可。這樣可以確保所有元素都被正確合併，並且保持排序。

var merge = function(nums1, m, nums2, n) {
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;

    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }

    while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p2--;
        p--;
    }
};

時間複雜度：O(m + n)，我們只需遍歷一次 nums1 和 nums2。
空間複雜度：O(1)，我們在原地進行合併，不需要額外的空間。

總結:
這道題目可以歸類為「Two Pointers」。與 26. Remove Duplicates from Sorted Array 和 27. Remove Element 類似，這些題目都需要在原地（in-place）更新陣列，因此使用雙指針來解題是最佳選擇。透過將每道 LeetCode 題目進行歸類和整理，我們可以發現 LeetCode 中確實存在一些解題模式。隨著解題數量的增加，相信讀者會越來越熟悉這些模式，從而更高效地解題，並同時加強自身的程式設計能力。