80. Remove Duplicates from Sorted Array II
同向双指针。Time: O(n), Space: O(1)
class Solution {
public int removeDuplicates(int[] nums) {
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (j == 0 || j == 1 || nums[i] != nums[j - 2]) {
nums[j++] = nums[i];
}
}
return j;
}
}
旧写法：
指针 i 遍历整个数组；
指针 j 指向下一个遇到的数放在什么位置，j 之前的数组是已经确定的，j 向右移动的条件是不满足当前数字和 j 左边两位数字重复。
class Solution {
public int removeDuplicates(int[] nums) {
int i = 0;
int j = 0;
while (j < nums.length) {
if (j == 0 || j == 1) {
nums[i++] = nums[j++];
} else if (nums[j] == nums[i - 2]) { // 这里的条件是 nums[j] == nums[i - 2]
j++;
} else {
nums[i++] = nums[j++];
}
}
return i;
}
}
class Solution:
def removeDuplicates(self, nums: 'List[int]') -> 'int':
if not nums or len(nums) < 3:
return len(nums)
# i: 遍历整个数组
# j 的物理意义：下一个遇到的数放在什么位置
# j 之前的数组是已经确定的
j = 2
for i in range(2, len(nums)):
if nums[j - 1] != nums[i] or nums[j - 2] != nums[i]:
nums[j] = nums[i]
j += 1
return j