iT邦幫忙

2025 iThome 鐵人賽

DAY 17
0
自我挑戰組

從零開始學習LeetCode系列 第 17

Day 17 Move Zeroes

  • 分享至 

  • xImage
  •  

題目:給定一個陣列 nums,需要把所有的 0 移到最後,並且保持非零元素的相對順序不變。
要求:就地修改(in-place),不要使用額外陣列
https://ithelp.ithome.com.tw/upload/images/20251002/20169339FyYFAisvSS.jpg


解法一:

  • 暴力解(交換移動)
  • 從頭到尾掃描,每當遇到 0,就把後面第一個非零元素往前換
  • 需要很多交換

解法二:
https://ithelp.ithome.com.tw/upload/images/20251002/20169339kISNw4t0Sb.jpg

  • 雙指針(最常見解法)
  • 程式碼簡單、效率高
  • 需要額外最後補 0

註解:

  • slow = 0 #建立一個指針,指向「非零數字應該放的位置」
  • for fast in range(len(nums)): #用 fast 指針遍歷整個陣列,每次檢查當前元素
  • if nums[fast] != 0: #當找到一個非零數字時,把它移動到 slow 的位置
  • nums[slow] = nums[fast] #把非零數字放到正確位置
  • slow += 1 #更新下一個非零數字應該放的位置
  • for i in range(slow, len(nums)):#當所有非零數字都處理完後,剩下的位置補上 0
  • nums[i] = 0 #從 slow 開始到陣列尾端,全部改成 0

解法三:
https://ithelp.ithome.com.tw/upload/images/20251002/20169339PgsmpOiwdW.jpg

  • 就地交換(簡化雙指針)
  • 不需要最後補 0
  • 缺點:多餘交換,效率略低於填充法。

註解:

  • slow = 0 #slow 指向下一個非零元素應該放的位置
  • for fast in range(len(nums)):#fast 從左到右遍歷整個陣列
  • if nums[fast] != 0: #只對非零元素做處理
  • nums[slow], nums[fast] = nums[fast], nums[slow] #將非零元素交換到 slow 位置
  • slow += 1 #移動空位指標到下一個位置,準備放下一個非零元素

上一篇
Day 16 股票題系列總整理
下一篇
Day 18 Rotate Array
系列文
從零開始學習LeetCode20
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言