LeetCode 筆記 - 88. Merge Sorted Array

Posted on 標籤
挑戰合併兩個已排序的數列。本文解析歸併排序（Merge Sort）的核心邏輯，透過比較兩數列首位元素依序放入結果中。文中特別分享 Python 內直接修改記憶體位置的語法技巧，達成原地合併且不浪費額外空間。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 88. Merge Sorted Array

給定兩個 Sorting 後的數列，請合併它們

解題思維

沒什麼特別的，就是 Merge sort 的一部分
持續取出兩個數列的第一個中最小的，直到全部取完

這裡有個小地方需要注意的是，不需要回傳結果，直接修改 nums1
可以使用以下寫法來直接修改

1
nums1[:] = result

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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.
        """
        
        nums1[:] = nums1[:m]
        nums2[:] = nums2[:n]
        
        result = []

        while nums1 and nums2:
            if nums1[0] < nums2[0]:
                value = nums1.pop(0)
            else:
                value = nums2.pop(0)
            result.append(value)

        if nums1:
            result.extend(nums1)
        if nums2:
            result.extend(nums2)
            
        nums1[:] = result

完成😊

也許你也會想看看