双指针:数组是有序的,那么重复的元素一定会相邻,删除重复元素,实际上就是将不重复的元素移到数组的左侧;
fast指针遍历数组,如果nums[fast] != nums[fast - 1],则nums[fast]和之前的元素都不同,则将nums[fast]的值复制到nums[slow],slow值加1,重复操作直至fast遍历完数组。
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int fast = 1, slow = 1;
while (fast < n) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
}
复杂度分析
- 时间复杂度:O(n)。
- 空间复杂度:O(1)。