Remove Duplicates from Sorted Arrays

Remove Duplicates from Sorted Arrays

Problem description

First approach: Case analysis

int removeDuplicates(vector<int>& nums) {
    if (nums.size() <= 1) return nums.size();
    nums.push_back(nums[nums.size()-1]);
    int l=0;
    bool d=false;
    for(int j=1, prev=nums[0];j<nums.size();++j) {
        if (!d && nums[j]==prev) d=true, ++l;
        else if (d && nums[j]!=prev) nums[l++] = prev = nums[j];
        else if (!d && nums[j]!=prev) prev=nums[++l];
    }
    return l;
}

Better approach: Step counting

int removeDuplicates(vector<int>& nums) {
    int count=0;
    for(int i=1;i<nums.size();++i) {
        if (nums[i]==nums[i-1]) ++count;
        else nums[i-count] = nums[i];
    }
    return nums.size()-count;
}

Similar problem: Remove elements with specific value Problem description

int removeElement(vector<int>& nums, int val) {
    int count=0;
    for(int i=0;i<nums.size();++i) {
        if (nums[i]==val) {
            ++count;
        } else {
            nums[i-count]=nums[i];
        }
    }
    return nums.size()-count;
}

Similar problem: Remove duplicates allowing at most 2 occurrences Problem description

int removeDuplicates(vector<int>& nums) {
    if (nums.size()<=1) return nums.size();
    int i=0;
    for(auto n : nums) {
		// Make sure third duplicate never enters [0~i]
        if (i<2 || n>nums[i-2]) nums[i++]=n;
    }
    return i;
}

#array