來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii
題目描述：
給你一個(gè)有序數(shù)組 nums ，請(qǐng)你原地刪除重復(fù)出現(xiàn)的元素，使每個(gè)元素最多出現(xiàn)兩次 ，返回刪除后數(shù)組的新長(zhǎng)度不恭。
不要使用額外的數(shù)組空間缠诅，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成宿礁。
說(shuō)明：
為什么返回?cái)?shù)值是整數(shù)拂封，但輸出的答案是數(shù)組呢茬射？
請(qǐng)注意，輸入數(shù)組是以「引用」方式傳遞的冒签，這意味著在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見(jiàn)的在抛。
你可以想象內(nèi)部操作如下:
// nums 是以“引用”方式傳遞的。也就是說(shuō)萧恕，不對(duì)實(shí)參做任何拷貝
int len = removeDuplicates(nums);
// 在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見(jiàn)的刚梭。
// 根據(jù)你的函數(shù)返回的長(zhǎng)度, 它會(huì)打印出數(shù)組中 該長(zhǎng)度范圍內(nèi) 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
輸入：nums = [1,1,1,2,2,3]
輸出：5, nums = [1,1,2,2,3]
解釋：函數(shù)應(yīng)返回新長(zhǎng)度 length = 5, 并且原數(shù)組的前五個(gè)元素被修改為 1, 1, 2, 2, 3 票唆。 不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素朴读。
示例 2：
輸入：nums = [0,0,1,1,1,1,2,3,3]
輸出：7, nums = [0,0,1,1,2,3,3]
解釋：函數(shù)應(yīng)返回新長(zhǎng)度 length = 7, 并且原數(shù)組的前五個(gè)元素被修改為 0, 0, 1, 1, 2, 3, 3 。 不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素走趋。
思路：
因?yàn)榭臻g復(fù)雜度要求為O(1),所以只能在原數(shù)組上進(jìn)行操作衅金，這就代表了至少需要2個(gè)指針，fast指向當(dāng)前正在掃描的數(shù)據(jù)索引簿煌，slow指向已經(jīng)‘有序’的索引氮唯。題目要求每個(gè)元素最多只能重復(fù)2次，也就是說(shuō)姨伟，前2個(gè)元素必然是可以保留的惩琉，所以我們fast和slow可以從第三個(gè)元素開(kāi)始
注意：數(shù)組是有序的
- slow = 2, fast = 2
- 判斷nums[slow - 2] == nums[fast] 是否相等
- 如果想等，說(shuō)明nums[slow]重復(fù)出現(xiàn)了3次
- 不相等夺荒，說(shuō)明nums[fast]元素符合要求瞒渠，放到slow位置num[slow] = nums[fast]，增加‘有序’邊界slow++
-
數(shù)組遍歷完返回slow
80般堆，刪除有序數(shù)組中的重復(fù)項(xiàng) II.png
實(shí)現(xiàn)：
class Solution {
public int removeDuplicates(int[] nums) {
int slow = 2, fast = 2;
for (fast = 2; fast < nums.length; fast++) {
if (nums[slow - 2] != nums[fast]) {
nums[slow++] = nums[fast];
}
}
return slow;
}
}
