26 删除有序数组中的重复项
指路[通用框架],通用框架用于解决删除重复项问题
slow指向未重复元素,此处slow = -1对应slow = dummyNode,fast = 0对应fast = head
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = -1, fast = 0;
while(fast < nums.size()){
if(fast + 1 < nums.size() && nums[fast] == nums[fast + 1]){
while(fast + 1 < nums.size() && nums[fast] == nums[fast + 1])
fast++;
}else{
slow++;
nums[slow] = nums[fast];
fast++;
}
}
// slow指向最后一个非重复元素,非重复元素链表为[0, slow],长度为slow + 1
return slow + 1;
}
};
由于题目已经说了“每个元素只出现一次”,所以不用担心会删掉第一个元素。这种情况下,我们不需要让slow指向-1(dummyNode),而是直接让slow指向head。
slow指向head后,fast只需要和slow比较即可
nums[slow] == nums[fast],那么fast跳过重复元素,fast++nums[slow] != nums[fast],那么将不重复元素加入到slow中