Leetcode刷題日記 - #88 Merge Sorted Array

1. Sorted Array：大多數的時候，解題的關鍵在，是不是能夠在看到題目的當下，迅速辨識「這題在問什麼」。看到“Sorted” Array的時候，大多數都在問2 pointer
2. 2 pointer的題目，要用畫圖去想比較容易一些，不然index數字很容易讓腦子很混亂，先自己用視覺的方式跑過一遍再寫解法，面試官也比較容易懂。
3. 最後關鍵，比較長的那個Array有在屁股留下足夠的空間塞數字，根據2，有個pointer一定是要指屁股，從尾巴路指到頭。會有一個pointer要指在nums1，一個在nums2，這樣才能比大小去merge，一樣也是從尾巴指到頭。

假設題目為兩個Array, nums1 = [1,2,3,0,0,0] nums2= [2,5,6]

我有3個pointer，他們的功能分別是

p3 = 負責指著儲存的空間

p1 = 負責指num1

p2 = 負責指num2

比較p1和p2，比較大的就塞進去p3的空間，直得注意的是，p1和p2是否要往前移動，在於我們塞了哪一個。用畫的比較快

最後，即使P1已經沒有數字可以指，如果P2還有數字可以指的話，要持續地塞進去P3，不然nums1裡面就會缺了nums2裡面的數字！

4. 解法：

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1 = m - 1
        p2 = n -1
        p3 = m + n - 1
        while p1 >= 0 and p2 >= 0:
            if nums2[p2] > nums1[p1]:
                nums1[p3] = nums2[p2]
                p2 -= 1
                p3 -= 1
            else:
                nums1[p3] = nums1[p1]
                p1 -= 1
                p3 -= 1
        # 處理P2還有數字可指的狀態
        while p2 >= 0:
            nums1[p3] = nums2[p2]
            p3 -= 1
            p2 -= 1

結語：看到Sorted Array就要往2 point方向去想，如果覺得很亂用畫圖的比較容易懂。