iT邦幫忙

2025 iThome 鐵人賽

DAY 26
0
自我挑戰組

用java解Leetcode系列 第 26

用java解Leetcode Day26

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20251010/201695013s1X7gv2He.pnghttps://ithelp.ithome.com.tw/upload/images/20251010/20169501n0IlSNGCsL.png

  1. Remove Duplicates from Sorted Array
    這題的核心是要求在原地(in-place)移除已排序陣列中的重複元素,並返回不重複元素的數量k。目標是處理一個已按非遞減順序排序的整數陣列nums,並達成以下兩點:
    一. 原地移除重複項(In-place Removel):不能使用額外的陣列來儲存結果。所有的操作必須直接在輸入陣列nums上進行。
    二. 保持相對順序:每個唯一的元素只能出現一次,且它們在陣列中的相對順序必須保持不變。
    如果唯一元素的數量是k,則函式需要將nums的前k個位置修改為包含所有唯一元素,並保持它們原有的順序。之後返回k(唯一元素的數量)。陣列中第k個元素之後的內容不重要。

因為陣列已經是排序好的,這是解決這個問題的關鍵。重複的元素會彼此相鄰。所以可以利用這一特性,使用雙指標(Two Pointers)的方法在O(n)時間複雜度和O(1)額外空間複雜度下解決問題。
首先,設置兩個指標:
慢指標(i或uniqueIndex):追蹤下一個唯一元素應該放置的位置。它同時也代表了目前找到的唯一元素的總數k。
快指標(j或runner):用來遍歷整個陣列,尋找新的唯一元素。
設置完後,初始化慢指標I = 0。而快指標j從1開始遍歷陣列到結尾。在每一步,比較nums[i]和nums[j]:如果nums[i]≠nums[j],這表示nums[j]是一個新的唯一元素。這時將慢指標i向前移動一步(i++),而這個新的唯一元素nums[j]賦值給新的唯一元素位置nums[i](即nums[i] = nums[j]);如果nums[i] = nums[j],這表示nums[j]是重複元素。這時不移動慢指標i,直接讓快指標j繼續向前移動,直到找到下一個不同的值。
迴圈結束後,慢指標i所在的位置就是唯一元素的最後一個索引。因此,唯一元素的總數k就是i + 1。


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

尚未有邦友留言

立即登入留言