iT邦幫忙

2025 iThome 鐵人賽

DAY 23
0
自我挑戰組

從零開始學習LeetCode系列 第 23

Day 23 Remove Duplicates from Sorted Array

  • 分享至 

  • xImage
  •  

題目:給你一個 已排序好的陣列 nums,請你「原地」移除重複元素,
使每個元素只出現一次,並返回移除後的新長度。

  • 不允許使用額外的陣列空間,只能在原陣列操作
  • https://ithelp.ithome.com.tw/upload/images/20251007/20169339Pt5nFjoJH5.jpg

解法一
https://ithelp.ithome.com.tw/upload/images/20251007/201693395145SKAYtb.jpg

  • 思路清楚但效率差
  • 每刪一次都需要重新排列

註解

  • 用 while 逐一比較當前與下一個元素
  • 若重複就刪除下一個
  • 若不同就繼續往後
  • 因為 pop() 很慢 → 時間複雜度 O(n²)

理解

  • 想像你在清理書櫃裡的重複書:
    你一邊看一邊刪,刪一本後後面的書要往前移,
    動作多又慢,但邏輯簡單

解法二
https://ithelp.ithome.com.tw/upload/images/20251007/201693391qkY4xV9NF.jpg

  • 雙指針法
  • 真正理解「原地修改」的經典題
  • 效率高 O(n)、順序保留

註解

  • slow:用來標記「目前最後一個不重複元素」的位置
  • fast:持續往後找「下一個不同的值」
  • 每找到新的數字,就更新 nums[slow + 1]
  • 結束時,slow + 1 就是新陣列的長度

理解

  • 就像整理書時:
    (1)左邊是「整理好」的一排書(slow)
    (2)右邊是「還沒檢查」的書(fast)
    (3)每當發現新書(不一樣的),就放到整理區的右邊

解法三
class Solution:
def removeDuplicates(self, nums):
unique = sorted(set(nums))
nums[:len(unique)] = unique
return len(unique)

  • 集合法
  • 使用集合輔助(雖不允許,但理解用)

這樣寫一行就完成,但不符「原地操作」要求。
不過它可以幫你驗證答案是否正確,是學習時很好的對照方法


上一篇
Day 22 Remove Element
系列文
從零開始學習LeetCode23
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言