- 題目
給你一個 非嚴格遞增排列 的數組 nums ,請你原地刪除重復出現的元素, 使每個元素 只出現一次 ,返回刪除后數組的新長度。 元素的 相對順序 應該保持 一致 然后返回 nums 中唯一元素的個數。
- 示例
示例 1:輸入:nums = [1,1,2] 輸出:2, nums = [1,2,_] 解釋:函數應該返回新的長度 2 ,并且原數組 nums 的前兩個元素被修改為 1, 2 。不需要考慮數組中超出新長度后面的元素。 示例 2:輸入:nums = [0,0,1,1,1,2,2,3,3,4] 輸出:5, nums = [0,1,2,3,4] 解釋:函數應該返回新的長度 5 , 并且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4 。不需要考慮數組中超出新長度后面的元素。
- 解題思路
- 因為數據是非嚴格遞增,也就是說數組是非遞減的。那么可以保證:后面的一定大于等于前面的元素。
- 那么就可以通過兩個指針。
- 第一個指針記錄結果數組的位置,同時表示結果數組的長度。從0位置開始(題目要求結果都在數組前部分)。
- 第二個指針依次遍歷每一個元素,看是否存在相同的元素。
- 這里是如何判斷的:因為我們通過第一個指針記錄了最終結數組的當前位置。那么這個位置及前面的元素可定是不相同的,并且一定大于前面的元素。那么在第二個指針遍歷元素的時候,如果是滿足條件,那么一定不和第一個指針指向的值相等。如果等于,那么表示重復元素,跳過該元素,繼續遍歷,直至末尾。
- 在第二個指針遍歷的過程中,遇到不相等的不重復的,就移動第一個指針記錄新元素。
- 代碼(Java)
class Solution {public int removeDuplicates(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int i = 0;int j = i + 1;while (i < nums.length && j < nums.length) {if (nums[i] != nums[j]) {nums[i + 1] = nums[j];i++;}j++;}return i + 1;} }