80. 刪除排序數(shù)組中的重復項 II
給定一個排序數(shù)組我碟，你需要在原地刪除重復出現(xiàn)的元素，使得每個元素最多出現(xiàn)兩次，返回移除后數(shù)組的新長度秕衙。
不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 額外空間的條件下完成僵刮。
示例 1:
給定
,
函數(shù)應返回新長度
, 并且原數(shù)組的前五個元素被修改為
据忘。
你不需要考慮數(shù)組中超出新長度后面的元素。
示例 2:
給定
,
函數(shù)應返回新長度
, 并且原數(shù)組的前五個元素被修改為
搞糕。
你不需要考慮數(shù)組中超出新長度后面的元素勇吊。
說明:
為什么返回數(shù)值是整數(shù)，但輸出的答案是數(shù)組呢?
請注意窍仰，輸入數(shù)組是以“引用”方式傳遞的汉规，這意味著在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的。
你可以想象內(nèi)部操作如下:
// nums 是以“引用”方式傳遞的驹吮。也就是說针史，不對實參做任何拷貝 int len = removeDuplicates(nums);
// 在函數(shù)里修改輸入數(shù)組對于調(diào)用者是可見的。
// 根據(jù)你的函數(shù)返回的長度, 它會打印出數(shù)組中該長度范圍內(nèi)的所有元素碟狞。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
解法
使用快慢指針啄枕，快指針每次循環(huán)都往前推進，慢指針只有在指針位置小于2（前面兩位必然需要向前推進）或者慢指針前推2位的數(shù)小于快指針的數(shù)時族沃，才向前推進频祝，并且將快指針的值賦值到慢指針位置。
源碼
class Solution {
public int removeDuplicates(int[] nums) {
int fast=0;
int slow=0;
while(fast<nums.length) {
//慢指針只有在小于2或者前數(shù)2位小于快指針時才往前推進
if (slow < 2 || nums[fast] > nums[slow-2]) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
