題目描述

給定一個遞增排序的nums整數陣列,用原地(in-place)的方式移除重複的元素,使每個元素都是獨特的,也就是只會出現一次。元素的相對位置在處理後應保持相同。



由於在某些程式語言中,更改陣列的長度是做不到的,您必須讓結果放置在nums陣列的前端。更準確地說,如果處理之後剩下k個元素,nums陣列的前k個元素就是最終結果,不會去管第k個元素之後的內容。

nums陣列的前k個元素為最終結果,k這個數值需被回傳。

不要配置額外的陣列空間,您必須在空間複雜度為#{{ O(1) }}#的條件下修改輸入的陣列。

原題網址

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

輸入格式

  • 1 <= nums.length <= 3 * 104
  • -100 <= nums[i] <= 100
  • nums為遞增排序。

輸出格式

回傳k,處理原來的nums陣列。

範例輸入1

nums = [1, 1, 2]

範例輸出1

2, nums = [1, 2, _]

範例輸入2

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

範例輸出2

5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

題解

這題要注意的是輸入的陣列是遞增排序的,因此我們可以使用兩個變數作為指標,一個用於走訪陣列,另一個用於指向已儲存的非重複之元素的最終索引位置。一旦走訪到與最後一個非重複的元素不同的元素,就把非重複之元素的最終索引位置加一,接著將該元素填入至該索引值的位置上。

最後再將非重複之元素的最終索引位置加一,就是這個擁有非重複元素的陣列之長度了。

參考答案