iT邦幫忙

2025 iThome 鐵人賽

DAY 27
0
自我挑戰組

用java解Leetcode系列 第 27

用java解Leetcode Day27

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20251011/20169501SX7jsmIOec.pnghttps://ithelp.ithome.com.tw/upload/images/20251011/20169501nR0sgoz1jQ.png

  1. Remove Element
    這題跟我上一篇很相似,不同的是,上一篇是移除陣列中的重複元素,而這一次是給定一個值,然後移除陣列中跟這個值相同的元素,其他都大致相同。
    詳細地說,這題給定一個整數陣列nums和一個目標值val,要求達成以下目標:
    1. 就地移除(In-place Removal):在不使用額外陣列空間的情況下,修改原地陣列nums,將所有等於val的元素移除。
    2. 計算並回傳k:回傳修改後陣列中不等於val的元素數量k。
    3. 重新排列陣列:確保原陣列nums的前k個位置(即nums[0]到nums[k-1])包含所有不等於val的元素。
    這題有以下三個限制:
    1. 就地(In-place):這表示不能創建一個新的陣列來儲存結果。必須直接在nums陣列上操作。
    2. 元素順序可變:題目允許不等於val的元素的相對順序可以改變。這是一個重要的寬鬆條件,讓解法更簡潔。
    3. 後續元素不重要:在nums[k]之後的元素(即第k個元素之後)可以是任何值,它們的值和數量都不影響結果的正確性。

處理這種需要就地修改且允許順序改變的陣列問題,雙指針(Two Pointers)是一個非常有效且常見的技巧。首先設置兩個指標i和k來遍歷陣列,i用來遍歷整個陣列,檢查每個元素nums[i]是否等於val。k用來指向下一個合格元素(即不等於val的元素)應該被寫入的位置。同時,k的最終值就是要回傳的合格元素總數。
接著,初始化k = 0(寫入位置,同時也是計數器)。
再來,使用i從頭到尾遍歷陣列。如果nums[i]不等於val(合格元素),將nums[i]的值複製到nums[k]的位置(nums[k] = nums[i]),然後,將寫入指標k向後移動一位(k++),準備接收下一個合格元素;如果nums[i]等於val(不合格元素),那就什麼都不做,因為只是要「跳過」或「移除」它。此時k保持不動,nums[i]的值會被後續的合格元素覆蓋。
遍歷結束後,k的值就是不等於val的元素的總數量,並且前k個元素已經被正確地排列。

複雜度分析
時間複雜度(Time Complexity):O(n)。這題只使用了一個for迴圈,遍歷了陣列中的n個元素一次。

空間複雜度(Space Complexity):O(1)。這題只使用了固定的額外空間來儲存兩個指標i和k,沒有創建與輸入大小相關的新陣列。這完全符合「就地(in-place)」的要求。


上一篇
用java解Leetcode Day26
系列文
用java解Leetcode27
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言