LeetCode 26 删除有序数组中的重复项
🟡 中等
https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/description/
思路
左侧指针 left 为写入位置，右侧指针 right 向右遍历。 pre记录上一位的值，count 记录当前pre 的count。
- right 每次向右移动一位
- nums[right] 和 pre 比较
- 相同 检查 count
- 不同 count 重置为1
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int left = 0,right = 0;//left next loc;
int n = nums.size();
int left_count = 0;
int pre = 10001;
while(right<n){
if(nums[right]==pre){
if(left_count==2){
}else{
nums[left] = nums[right];
pre = nums[left];
left_count++;
left++;
}
}else{
nums[left] = nums[right];
pre = nums[left];
left_count = 1;
left++;
}
right++;
}
cout<<left<<endl;
return left - 0+1-1;
}
};
可以优化
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if(n<3) return n;
int slow = 2,fast = 2;
while(fast<n){
if(nums[slow-2]!=nums[fast]){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow-1-0+1;
}
};
- java 版本
- 按照栈的思路，
- 当前元素 如果和栈下面的第二个元素不等， 那么可以入栈
class Solution {
public int removeDuplicates(int[] nums) {
int stackCursor = 2;
int fast = 2;
while (fast<=nums.length-1){
if(nums[fast]!=nums[stackCursor-2]){
nums[stackCursor++] = nums[fast];
}
fast++;
}
return Math.min(stackCursor-1-0+1,nums.length);
}
}