【LeetCode】Merge Sorted Array - 把兩個陣列縫起來 - 陣列、雙指針、經典題 - 都會阿嬤 (@weikaiwei)

【LeetCode】Merge Sorted Array - 把兩個陣列縫起來 - 陣列、雙指針、經典題

網頁好讀版：

## 題目 LeetCode 88

## 思路 1. 要把兩個已經排序好的陣列合起來，最簡單的方法就是先不管三七二十一，把兩個陣列接起來後，再做排序 2. 記住這邊是 in-place 的，所以我們要用到 nums1 後面保留 0 的空間來放 nums2 的數字，再做排序 3. 因為是in-place的，所以要用 nums1.sort()，不能用sorted(nums1) 4. 由以上可以得到 **解法一** 5. 解法一要對一個大陣列做排序，所需要的時間是$O(N~log~N)，N=m+n$ 6. 既然兩個陣列都已經排序好了，我們可以從 nums1 和nums2 的開頭開始比較，並且拿比較小的那個數放到 nums1 裡 7. 但是這樣會邊讀邊改到nums1，所以我們可以再開一個額外的陣列先把 nums1 的數字存起來 8. 這樣我們就可以有一個時間複雜度為 $O(m+n)$ 的解法，但因為我們有用額外的記憶體來儲存 nums1，所以會有額外的空間複雜度 $O(m)$ 9. 我們可以寫出 **解法二** 10. 事實上還有更有效率的解法，可以不花額外記憶體並且也是時間複雜度 $O(m+n)$，這個 follow-up 我之後跟其他類題一起講解 ## 解法一 ``` python= 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. """ #Solution 1, Naive for i in range(n): nums1[m+i] = nums2[i] nums1.sort() ``` ## 解法二 ``` python= 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. """ storage = nums1[:m] p1 = 0 p2 = 0 for i in range(n+m): if p1 == m: nums1[i:] = nums2[p2:] break if p2 == n: nums1[i:] = storage[p1:] break if storage[p1] <= nums2[p2]: nums1[i] = storage[p1] p1 += 1 else: nums1[i] = nums2[p2] p2 += 1 ``` ## 筆記 * 這題其實不難，重點是循序漸進難度遞增，並且會有不同的時間複雜度和空間複雜度的考量，所以很適合當作一個面試的題目 (LeetCode 上面討論的)，如果你在面試有遇到這個問題，歡迎在下面留言 * HackMD 筆記: