Yoru Karu Studio
Yoru Karu Studio

LeetCode 解題思路：88. Merge Sorted Array（合併兩個有序數組）

從後往前的巧妙思維：原地合併的藝術

luk 收錄於 Leetcode
 約 1700 字 預計閱讀 8 分鐘 

LeetCode 解題思路：Merge Sorted Array（合併兩個有序數組）

題目描述

給你兩個按非遞減順序排列的整數數組 nums1 和 nums2，另有兩個整數 m 和 n，分別表示 nums1 和 nums2 中的元素數目。

請你合併 nums2 到 nums1 中，使合併後的數組同樣按非遞減順序排列。

注意：最終的排序數組不應由函數返回，而是儲存在數組 nums1 中。為了應對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應合併的元素，後 n 個元素為 0，應忽略。nums2 的長度為 n。

範例

範例 1：

輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
解釋：需要合併 [1,2,3] 和 [2,5,6]
結果是 [1,2,2,3,5,6]

範例 2：

輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
解釋：需要合併 [1] 和 []
結果是 [1]

範例 3：

輸入：nums1 = [0], m = 0, nums2 = [1], n = 1
輸出：[1]
解釋：需要合併 [] 和 [1]
結果是 [1]
注意：由於 m = 0，nums1 中沒有元素。nums1 中僅存的 0 只是為了確保合併後結果可以儲存在 nums1 中

限制條件

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

核心概念

1. 問題本質分析

關鍵洞察：

  • 原地合併：必須在 nums1 中完成，不能使用額外空間
  • 已預留空間：nums1 後面有 n 個位置是空的
  • 從後往前：避免覆蓋還未處理的元素

2. 為什麼從後往前？ 

從前往後（錯誤示範）：
nums1 = [1,2,3,0,0,0], nums2 = [2,5,6]

如果從前往後：
比較 1 和 2，選 1，但放哪裡？
如果放在 nums1[0]，沒問題
比較 2 和 2，選哪個都行，但如果要插入 nums2[0] 的 2，
會覆蓋 nums1[1] 的 2，而它還沒被處理！

從後往前（正確方法）：
nums1 = [1,2,3,0,0,0], nums2 = [2,5,6]
                  ↑
              填充位置

比較 3 和 6，選 6，放在最後
nums1 = [1,2,3,0,0,6]
               ↑
           下個位置

3. 視覺化理解 

初始狀態：
nums1: [1, 2, 3, 0, 0, 0]  m = 3
        ↑     ↑        ↑
       i=0   i=2      p=5

nums2: [2, 5, 6]  n = 3
        ↑     ↑
       j=0   j=2

從後往前填充過程：
步驟 1: 比較 nums1[2]=3 和 nums2[2]=6
       6 > 3，放入 6
       [1, 2, 3, 0, 0, 6]

步驟 2: 比較 nums1[2]=3 和 nums2[1]=5
       5 > 3，放入 5
       [1, 2, 3, 0, 5, 6]

...依此類推

解法一：三指標從後往前（最優解）

思路

使用三個指標：

  • i：指向 nums1 有效元素的末尾
  • j：指向 nums2 的末尾
  • p：指向 nums1 的末尾（填充位置）

程式碼實現 

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.
        """
        # 三個指標的初始位置
        i = m - 1  # nums1 有效元素的最後位置
        j = n - 1  # nums2 的最後位置
        p = m + n - 1  # 合併後數組的最後位置
        
        # 從後往前比較並填充
        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[p] = nums1[i]
                i -= 1
            else:
                nums1[p] = nums2[j]
                j -= 1
            p -= 1
        
        # 如果 nums2 還有剩餘元素，全部複製過去
        while j >= 0:
            nums1[p] = nums2[j]
            j -= 1
            p -= 1
        
        # 如果 nums1 還有剩餘元素，它們已經在正確位置，無需處理

執行過程詳解 

def merge_with_trace(nums1, m, nums2, n):
    """帶追蹤的合併過程"""
    i, j, p = m - 1, n - 1, m + n - 1
    
    print(f"初始: nums1={nums1}, nums2={nums2}")
    print(f"指標: i={i}, j={j}, p={p}")
    
    step = 1
    while i >= 0 and j >= 0:
        print(f"\n步驟 {step}: 比較 nums1[{i}]={nums1[i]} 和 nums2[{j}]={nums2[j]}")
        
        if nums1[i] > nums2[j]:
            print(f"  選擇 nums1[{i}]={nums1[i]}")
            nums1[p] = nums1[i]
            i -= 1
        else:
            print(f"  選擇 nums2[{j}]={nums2[j]}")
            nums1[p] = nums2[j]
            j -= 1
        
        p -= 1
        print(f"  結果: {nums1}")
        step += 1
    
    # 處理剩餘元素
    while j >= 0:
        print(f"\n步驟 {step}: 複製剩餘的 nums2[{j}]={nums2[j]}")
        nums1[p] = nums2[j]
        j -= 1
        p -= 1
        print(f"  結果: {nums1}")
        step += 1

# 測試
nums1 = [1,2,3,0,0,0]
merge_with_trace(nums1, 3, [2,5,6], 3)

解法二：簡化版本（利用 Python 特性）

思路

Python 允許負索引，可以簡化代碼。

程式碼實現 

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 使用 while 的更簡潔寫法
        while m > 0 and n > 0:
            if nums1[m-1] > nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m -= 1
            else:
                nums1[m+n-1] = nums2[n-1]
                n -= 1
        
        # 如果 nums2 還有剩餘，直接複製
        if n > 0:
            nums1[:n] = nums2[:n]

解法三：使用內建函數（面試時要謹慎）

思路

直接複製後排序。

程式碼實現 

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 將 nums2 複製到 nums1 的後半部分
        nums1[m:m+n] = nums2
        # 原地排序
        nums1.sort()

注意：這個解法時間複雜度是 O((m+n)log(m+n))，不如前面的 O(m+n)

解法四：額外空間（不符合題目要求，但有教育意義）

思路

使用額外數組存儲結果。

程式碼實現 

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 創建副本
        nums1_copy = nums1[:m]
        
        # 雙指標合併
        i = j = 0
        for p in range(m + n):
            # 確定要複製的值
            if j >= n or (i < m and nums1_copy[i] <= nums2[j]):
                nums1[p] = nums1_copy[i]
                i += 1
            else:
                nums1[p] = nums2[j]
                j += 1

變化題型

1. 合併 k 個有序數組 

def mergeKArrays(arrays: List[List[int]]) -> List[int]:
    """
    使用最小堆合併 k 個有序數組
    """
    import heapq
    
    heap = []
    result = []
    
    # 初始化堆
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))
    
    # 合併
    while heap:
        val, arr_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        
        # 加入下一個元素
        if elem_idx + 1 < len(arrays[arr_idx]):
            heapq.heappush(heap, 
                (arrays[arr_idx][elem_idx + 1], arr_idx, elem_idx + 1))
    
    return result

2. 合併兩個有序鏈表（原地） 

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    """
    合併兩個有序鏈表
    """
    dummy = ListNode(0)
    current = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    
    # 連接剩餘部分
    current.next = l1 or l2
    
    return dummy.next

3. 找出合併後的中位數 

def findMedianAfterMerge(nums1: List[int], m: int, 
                         nums2: List[int], n: int) -> float:
    """
    不實際合併，直接找中位數
    """
    total = m + n
    if total % 2 == 1:
        return findKth(nums1, m, nums2, n, total // 2 + 1)
    else:
        return (findKth(nums1, m, nums2, n, total // 2) + 
                findKth(nums1, m, nums2, n, total // 2 + 1)) / 2.0

def findKth(nums1, m, nums2, n, k):
    # 二分查找第 k 小的數
    if m > n:
        return findKth(nums2, n, nums1, m, k)
    if m == 0:
        return nums2[k-1]
    if k == 1:
        return min(nums1[0], nums2[0])
    
    i = min(m, k // 2)
    j = k - i
    
    if nums1[i-1] < nums2[j-1]:
        return findKth(nums1[i:], m-i, nums2, n, k-i)
    else:
        return findKth(nums1, m, nums2[j:], n-j, k-j)

4. 合併但去除重複元素 

def mergeUnique(nums1: List[int], m: int, 
                nums2: List[int], n: int) -> int:
    """
    合併並去重，返回新長度
    """
    i, j, p = m - 1, n - 1, m + n - 1
    
    # 先正常合併
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[p] = nums1[i]
            i -= 1
        else:
            nums1[p] = nums2[j]
            j -= 1
        p -= 1
    
    while j >= 0:
        nums1[p] = nums2[j]
        j -= 1
        p -= 1
    
    # 去重
    if m + n == 0:
        return 0
    
    write = 1
    for read in range(1, m + n):
        if nums1[read] != nums1[read-1]:
            nums1[write] = nums1[read]
            write += 1
    
    return write

常見錯誤與陷阱

錯誤 1：從前往後合併 

# ❌ 錯誤！會覆蓋未處理的元素
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    i = j = p = 0
    while i < m and j < n:
        if nums1[i] <= nums2[j]:
            nums1[p] = nums1[i]  # 可能覆蓋未處理的元素！
            i += 1
        else:
            nums1[p] = nums2[j]
            j += 1
        p += 1

錯誤 2：忘記處理剩餘元素 

# ❌ 錯誤！沒有處理剩餘的 nums2
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    i = m - 1
    j = n - 1
    p = m + n - 1
    
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[p] = nums1[i]
            i -= 1
        else:
            nums1[p] = nums2[j]
            j -= 1
        p -= 1
    # 忘記處理 j >= 0 的情況！

錯誤 3：索引計算錯誤 

# ❌ 錯誤！索引越界
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    i = m  # 應該是 m - 1
    j = n  # 應該是 n - 1
    p = m + n  # 應該是 m + n - 1

錯誤 4：修改了 m 和 n 

# ❌ 不好的做法！使用 m 和 n 作為索引
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    while m > 0 and n > 0:
        if nums1[m-1] > nums2[n-1]:
            nums1[m+n-1] = nums1[m-1]
            m -= 1  # 修改了參數
        else:
            nums1[m+n-1] = nums2[n-1]
            n -= 1  # 修改了參數

複雜度分析

解法時間複雜度空間複雜度說明
三指標從後往前O(m+n)O(1)最優解
使用內建排序O((m+n)log(m+n))O(1)簡單但不夠高效
額外空間O(m+n)O(m)不符合題目要求

優化技巧

1. 減少比較次數 

def merge_optimized(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    i, j, p = m - 1, n - 1, m + n - 1
    
    # 當 nums1 處理完時，直接複製 nums2
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[p] = nums1[i]
            i -= 1
        else:
            nums1[p] = nums2[j]
            j -= 1
        p -= 1
    
    # 優化：使用切片賦值
    if j >= 0:
        nums1[:j+1] = nums2[:j+1]

2. 處理特殊情況 

def merge_with_edge_cases(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    # 特殊情況：nums2 為空
    if n == 0:
        return
    
    # 特殊情況：nums1 為空
    if m == 0:
        nums1[:] = nums2
        return
    
    # 特殊情況：nums1 最大值小於 nums2 最小值
    if nums1[m-1] <= nums2[0]:
        nums1[m:] = nums2
        return
    
    # 一般情況
    # ... 正常合併邏輯

相關題目推薦

  1. LeetCode 21: Merge Two Sorted Lists - 合併有序鏈表
  2. LeetCode 23: Merge k Sorted Lists - 合併 k 個有序鏈表
  3. LeetCode 4: Median of Two Sorted Arrays - 兩個有序數組的中位數
  4. LeetCode 148: Sort List - 排序鏈表（歸併排序）
  5. LeetCode 56: Merge Intervals - 合併區間
  6. LeetCode 977: Squares of a Sorted Array - 有序數組的平方

實戰技巧總結

1. 從後往前的模板 

def merge_from_end_template(arr1, m, arr2, n):
    i = m - 1  # arr1 的有效元素末尾
    j = n - 1  # arr2 的末尾
    p = m + n - 1  # 填充位置
    
    while i >= 0 and j >= 0:
        if arr1[i] > arr2[j]:
            arr1[p] = arr1[i]
            i -= 1
        else:
            arr1[p] = arr2[j]
            j -= 1
        p -= 1
    
    # 處理剩餘元素
    while j >= 0:
        arr1[p] = arr2[j]
        j -= 1
        p -= 1

2. 調試技巧 

def merge_debug(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    print(f"合併前：")
    print(f"  nums1[:m] = {nums1[:m]}")
    print(f"  nums2 = {nums2}")
    
    i, j, p = m - 1, n - 1, m + n - 1
    
    while i >= 0 and j >= 0:
        print(f"\n比較 nums1[{i}]={nums1[i]} 和 nums2[{j}]={nums2[j]}")
        if nums1[i] > nums2[j]:
            nums1[p] = nums1[i]
            i -= 1
        else:
            nums1[p] = nums2[j]
            j -= 1
        p -= 1
        print(f"當前結果：{nums1}")
    
    while j >= 0:
        nums1[p] = nums2[j]
        j -= 1
        p -= 1
    
    print(f"\n合併後：{nums1}")

3. 完整測試用例 

def test_merge():
    test_cases = [
        # (nums1, m, nums2, n, expected)
        ([1,2,3,0,0,0], 3, [2,5,6], 3, [1,2,2,3,5,6]),
        ([1], 1, [], 0, [1]),
        ([0], 0, [1], 1, [1]),
        ([2,0], 1, [1], 1, [1,2]),
        ([4,5,6,0,0,0], 3, [1,2,3], 3, [1,2,3,4,5,6]),
        ([1,2,4,5,6,0], 5, [3], 1, [1,2,3,4,5,6]),
        ([-1,0,0,3,3,3,0,0,0], 6, [1,2,2], 3, [-1,0,0,1,2,2,3,3,3]),
        ([0,0,0], 0, [1,2,3], 3, [1,2,3])
    ]
    
    for nums1, m, nums2, n, expected in test_cases:
        nums1_copy = nums1.copy()
        merge(nums1, m, nums2, n)
        status = "✅" if nums1 == expected else "❌"
        print(f"{status} 輸入: {nums1_copy[:m]} + {nums2}, 結果: {nums1}")

總結

這道合併有序數組的題目展示了：

  1. 空間利用技巧：充分利用預留空間
  2. 從後往前思維：避免覆蓋未處理元素
  3. 雙指標技巧：高效處理有序數據
  4. 原地算法：不使用額外空間完成任務

關鍵要點：

  • 理解為什麼要從後往前
  • 記得處理剩餘元素
  • 注意索引邊界
  • 善用語言特性簡化代碼

練習建議

  1. 基礎練習：

    • 手動模擬合併過程
    • 畫圖理解指標移動
    • 處理各種邊界情況

  2. 進階練習：

    • 實現合併 k 個數組
    • 嘗試不同的優化方法
    • 解決相關變形題

  3. 實際應用：

    • 歸併排序的實現
    • 外部排序算法
    • 數據流合併

記住：從後往前是處理原地合併的關鍵思維！

更新於 2024-12-03 
CC BY-NC-SA 4.0
閱讀原始文檔
LeetcodeAlgorithmArrayTwo-Pointers
返回 | 主頁
0%