跳转至

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中
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 0, fast = 0;
        while(fast < nums.size()){
            if(nums[slow] != nums[fast]){
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        // slow指向最后一个非重复元素,非重复元素链表为[0, slow],长度为slow + 1
        return slow + 1;
    }
};