今日題目

題目連結：88. Merge Sorted Array
題目主題：Array、Two Pointer、Sorting

今天要說說另一種排序法，這次選的題目個人覺得是很典型的 Insertion Sort 的例子，非常適合來練習這個排序法。

簡單說說 Insertion Sort

Insertion Sort是一種基本的排序方法，用一個雙迴圈處理排序的方法。以小到大的排序為例，Insertion Sort的每一圈都會往後走一步將前面的數字確認好排序，走到最後一個數字就能排好這個陣列的順序，處理的過程如下圖。

範例：nums = [32, 2, 18, 45, 15]

紅方框是每一圈處理的範圍，紅色數字是主要處理的值，這個值會一直往前去比對是否比較小，如果比較小就跟前面的數字換，圖中每一圈上方的黑色箭頭就是這個紅色數字走的過程，這個數字會一直走到前面的數字比較小才停下來，就像第五圈 15 的狀況，走了三步後因為2比較小，所以停在這。當然也有像第四圈的狀況，連走都不用走，45就剛好是這個範圍最大的值，所以不用動。

題目解説

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

本題目標是合併兩個數字陣列，並且將這個陣列做好正排序。而這兩個陣列分別為nums1, nums2，另外還會給 m 跟 n 這兩個值。

nums1 跟 nums2 再輸入時已經是正排序好的陣列
m+n 代表 nums1 的總長度
m 代表 nums1 中有數字的長度
n 代表 nums2 的長度

nums1 陣列中前 m 個元素皆為整數值，後 n 個元素為0來表示，這n個0不需被排進最終合併結果。

最後要注意的是，這個最終的輸出不會由方法的return回傳，而是修改到nums1陣列中來代表完成。

約束：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

範例1

輸入: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出: [1,2,2,3,5,6]
解釋: 可以看到輸出結果是[1,2,2,3,5,6]，nums1的0都被nums2的數字[2,5,6]取代後正排序後的結果。

範例2

輸入: nums1 = [1], m = 1, nums2 = [], n = 0
輸出: [1]
解釋: 如果 nums2 是空的，合併結果其實就是 nums1 本身，所以直接輸出[1]。

範例3

輸入: nums1 = [0], m = 0, nums2 = [1], n = 1
輸出: [1]
解釋: m 如果是 0 代表 nums1 沒有任何數字，nums1 有 0 是因為n有值，所以會補上這個0，應直接忽略這個0。因此合併後的結果就是 nums2 的所有值直接取代放進 nums1，最後輸出[1]。

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 排除 n = 0 的狀況，不需處理直接結束。
2. 排除 m = 0 的狀況，只需要將nums2中的值取代到nums1中對應的位置即可結束。
3. 跑一個雙迴圈
   • 第一層每一圈處理一個數字，將nums2的數字取代進nums1中對應的位置。
   • 第二層迴圈，將nums1新進來的數字跟前面的數字做排序。

圖解過程

範例：nums1 = [1, 2, 3, 0, 0, 0] , m = 3 , nums2 = [2, 5, 6] , n = 3

上圖中，紅色方框是每一圈處理範圍，每一圈都會從nums2把一個數字取代到nums1對應的位置，訂好它的位置以後會變綠色數字，而黑色箭頭就是紅色數字走的過程。最終上圖中輸出的部份，綠色的數字就是從nums2移動過來的數字。

其實過程跟Insertion Sort處理過程有90%像，只是每一次處理的目標數字是從另外一個陣列過來的數字，其餘過程都一樣。

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 忽略 n = 0 的狀況，因為nums1直接是完整的
        if n <= 0: return
        # m = 0 的狀況，要將nums2的值都取代近nums1中
        if m <= 0: 
            nums1[:] = nums2
            return
        # 這是Insertion Sort滿典型的樣子
        # 但過程是nums2的值插進nums1中來做排序
        for startIdx in range(m, m+n):
            nums1[startIdx] = nums2[startIdx-m]
            for idx in range(startIdx, 0, -1):
                if nums1[idx] >= nums1[idx-1]:
                    break
                tmp = nums1[idx]
                nums1[idx] = nums1[idx-1]
                nums1[idx-1] = tmp

希望您今天能瞭解到...

• Insertion Sort 基本概念
• 88. Merge Sorted Array 解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：20. Valid Parentheses