題目出處

88. Merge Sorted Array

難度

Easy

題目分類

array, two-pointers

個人範例程式碼

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        while(m > 0 && n > 0){
            if(nums1[m-1] >= nums2[n-1]){
                nums1[m+n-1] = nums1[m-1];
                m -= 1;
            }
            else{
                nums1[m+n-1] = nums2[n-1];
                n -= 1;
            }
        }
        while(n > 0){
            nums1[m+n-1] = nums2[n-1];
            n -= 1;
        }        
    }
};

說明

這題我們可以先注意題目的敘述：
最需要思考的部分在於「題目希望最後的結果直接儲存在 nums1 裡面」

雖然這樣的限制會使我們解題更加的「受到限制」，但反過來說，
其實這也是題目給我們「最大的提示」。

題目的 nums1 給的空間為 m+n，所以最後我們都會將所有的值擺入 nums1 中，
而因為我們可以無憂慮去更改的值為最後的 0,0,0… 部分
(因為這個值就算被改消失了，也不影響我們想計算的結果)

所以這邊可以推斷出一定要「從後面開始解」，「從最無痛的 0 開始取代」，

再來我們就可以來思考，什麼時候擺入 nums1的值? 什麼時候擺入 nums2 的值?
我們可以靠著題目所給的 m, n 來進行這樣的操作，透過值不斷擺入，
我們去移動 m, n 作為 index 的座標，即可順利完成此題目。

邊際情況處理

這題要注意的邊際情況為 m=0, n=0 的時候我們要怎麼處理，
而照題目的敘述，

• n=0 基本上對我們來說沒差，因為 m 控制的 nums1 即代表我們要的答案
• m=0 才是重點，如果還有剩餘的 n，都需要擺入 nums1 中，而位置索幸很好取得，
  依然可以透過 m+n-1 算出

注意 index 細節，才是這題要考細心的部分

這題有很多 index 細節考驗著作答者的細心度，
包含：

• 迴圈的範圍僅限於 m, n > 0 時，其他需要進例外處理
• m-1, n-1 才是當下座標
• 要擺入的位置為 m+n-1
• 處理到 n > 0 就應該停下，而非 n >= 0

Reference

• Python easy to understand in-place solution