1.题目描述:
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
2.题解思路:
注意到数组是有序的,所以重复的元素一定是相邻的。
题目要求在原地删除重复出现的元素,其实就是将后边不重复的元素移动到前边,替代那些重复的元素。
也就是说,遇到重复元素不做处理,遇到不重复元素才往前覆盖。
可以考虑使用双指针法(快慢指针)。快指针从第二个元素开始(下标1)遍历数组中所有的元素,慢指针指向最后一个不重复的元素(初始为下标0)。
当快指针j指向的值和慢指针i指向的值相等时,说明快指针指向的是重复元素,所以慢指针不动(因为下一个就是重复元素了,而慢指针指向的是不重复元素),快指针自增。
当快指针j指向的值和慢指针i指向的值不相等时,说明快指针指向的是不重复元素,需要将这个不重复元素覆盖到第一个重复元素的位置(也就是慢指针的下一个位置),再将快指针自增。
3.代码实现:
public int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[i] != nums[j]) {
nums[++i] = nums[j];
}
}
return i + 1;
}
复杂度分析:
- 时间复杂度:O(n),假设数组的长度是n,需要遍历n步。
- 空间复杂度:O(1),不需要额外开辟新的空间。