Saturday, July 22, 2017

Remove Duplicates from Sorted Array II



Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1122 and 3. It doesn't matter what you leave beyond the new length.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int count = 1;
        int ans = 0, size = nums.size();
        if (size == 0 || size == 1) {
            return size;
        }
     
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums[i] != nums[i + 1]) {
                nums[ans++] = nums[i];
                count = 1;
            } else {
                count++;
                if (count == 2) {
                    nums[ans++] = nums[i];
                }
            }
        }
        nums[ans] = nums[size - 1];
        return ans + 1;
    }
};

============= Another attempt ==========
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int size = 0, iter = 1, count = 1;
       
        if (nums.size() == 0) {
            return size;
        }
       
        while (iter < nums.size()) {
            if (nums[iter] == nums[size]) {
                count++;
                if (count == 2) {
                    nums[size + 1] = nums[iter];
                    size++;
                }
            } else {
                count = 1;
                nums[size + 1] = nums[iter];
                size++;
            }
            iter++;
        }
        nums.resize(size + 1);
        return size + 1;
    }
};

============= Optimized ==============
class Solution { public: int removeDuplicates(vector<int>& nums) { if(nums.size()<3) return nums.size(); int index=2; for(int i=2;i<nums.size();i++){ if(nums[i]!=nums[index-2]) nums[index++] = nums[i]; } return index; } };

No comments:

Post a Comment