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

tags: leetcode

https://leetcode.com/problems/merge-sorted-array/description/

題目 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 我之後跟其他類題一起講解

解法一

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()

解法二

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 筆記: https://hackmd.io/@ga642381/r1sE8IsKj