iT邦幫忙

2025 iThome 鐵人賽

DAY 25
0
自我挑戰組

從零開始學習LeetCode系列 第 25

Day 25 Merge Sorted Array

  • 分享至 

  • xImage
  •  

題目:給定兩個 排序好的整數陣列 nums1 和 nums2,
其中:

  • nums1 的長度足夠容納兩個陣列的所有元素
  • m 為 nums1 的有效長度
  • n 為 nums2 的長度

將 nums2 合併到 nums1 中,使 nums1 仍然是排序後的結果
https://ithelp.ithome.com.tw/upload/images/20251008/201693395aVcyEBg5b.jpg


解法一
https://ithelp.ithome.com.tw/upload/images/20251008/201693390GNpEOBpuG.jpg

  • 簡單、容易理解

註解

  • 先把 nums2 直接放到 nums1 的尾端空位
  • 再整體排序
  • 雖然簡單,但效率低,因為 sort() 是 O((m+n)log(m+n))。

理解

  • 就像把兩疊已排序的卡片全部倒在桌上再重新排一次

解法二
https://ithelp.ithome.com.tw/upload/images/20251008/20169339CUCDBvzEKi.jpg

  • 雙指針(前往後)
  • 清楚明瞭,但需要額外陣列空間

註解

  • 設兩個指針 i(指向 nums1)與 j(指向 nums2)
  • 比較兩陣列當前值,較小者加入結果陣列
  • 最後再接上剩下的元素
  • 時間複雜度 O(m+n)

理解

  • 就像你在合併兩疊已排序的卡片,每次都從兩邊挑最小的一張放入新牌堆

解法三
https://ithelp.ithome.com.tw/upload/images/20251008/20169339CKc2UDfwWj.jpg

  • 雙指針(後往前)
  • 空間最省,原地完成合併
  • 是這題的標準最佳解

註解

  • i 指向 nums1 的最後一個有效元素
  • j 指向 nums2 的最後一個元素
  • k 是總長度的最後一格(放置位置)
  • 從尾端開始比大小,將較大的放入 nums1[k]
  • 不需額外空間,時間 O(m+n)、空間 O(1)

理解

  • 想像兩個已排序的紙牌堆放在桌上,你從兩堆的最尾端開始比較,
    把「較大」的牌往後放,從右邊慢慢填滿

上一篇
Day 24 Remove Duplicates from Sorted Array II
下一篇
Day 26 Valid Parentheses
系列文
從零開始學習LeetCode27
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言