问题
RT, 要求原地删除,返回新数组长度即可。
算法:双指针
对应基础课的双指针算法,快指针在前面移动遍历,慢指针在后面更新答案
这里慢指针定义为新数组最后一个数的索引。由于是排好序的,所以快指针第一次遇到某个新的数就可以修改慢指针的下一个位置。
复杂度
时间:$O(N)$
空间:$O(1)$
代码
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size()==0) return 0;
int i, j;
for(i = 0, j = 0; i < nums.size(); i ++){
if(nums[i] != nums[j]){
nums[++j] = nums[i];
}
}
return j+1;
}
};