Showing posts with label Duplicates. Show all posts
Showing posts with label Duplicates. Show all posts

Wednesday, September 27, 2017

442. Find All Duplicates in an Array

https://leetcode.com/problems/find-all-duplicates-in-an-array/description/
Solution 1. swap number i to index i-1
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        int i=0;
        while(i<nums.size()) {
            if(nums[i] != nums[nums[i]-1])
                swap(nums[i], nums[nums[i]-1]);
            else i++;
        }
        for(int i=0; i<nums.size(); i++) {
            if(i+1 != nums[i]) res.push_back(nums[i]);
        }
        return res;
    }
Solution 2. Mark by +/-
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for(int i=0; i<nums.size(); i++) {
            nums[abs(nums[i])-1] = -nums[abs(nums[i])-1];
            if(nums[abs(nums[i])-1]>0) res.push_back(abs(nums[i]));
        }
        return res;
    }
Solution 3. counting number nums[i] by adding n to index i-1
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        int n = nums.size();
        for(int i=0; i<n; i++) {
            nums[(nums[i]-1)%n] += n;
        }
        for(int i=0; i<n; i++) {
            if(nums[i]>2*n) res.push_back(i+1);
        }
        return res;
    }

Thursday, September 14, 2017

605. Can Place Flowers

https://leetcode.com/problems/can-place-flowers/description/
Solution 1. add 0 to both side for convenience.
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        if(n == 0) return true;
        if(flowerbed.size() == 0) return false;
        flowerbed.insert(flowerbed.begin(),0);
        flowerbed.push_back(0);
        for(int i=1; i<flowerbed.size()-1; i++) {
            if(flowerbed[i-1] + flowerbed[i] + flowerbed[i+1] == 0) {
                i++;
                n--;
            }
        }
        return n<=0;
    }
Solution 2.
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        if(n == 0) return true;
        if(flowerbed.size() == 0) return false;
        int z = flowerbed[0] ? 0 : 2, res = 0; // a 0 at beginning counted as 2
        for(int i=1; i<flowerbed.size(); i++) {
            if(flowerbed[i] == 1 && flowerbed[i-1] == 0) {
                res += (z-1)/2;
                z = 0;
                if(res>=n) return true;
            }
            else if(flowerbed[i] == 0 && flowerbed[i-1] == 1) {
                z = 1;
            }
            else if(flowerbed[i] == 0) z++;
            else continue;
        }
        res += z/2;
        if(res>=n) return true;
        return false;
    }

Wednesday, August 30, 2017

645. Set Mismatch

https://leetcode.com/problems/set-mismatch/description/
Solution 0. Use XOR and count numbers
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> cnt(nums.size(),0);
        vector<int> res = {0, 0};
        for(int i=0; i<nums.size(); i++) {
            if(++cnt[nums[i]-1] == 2)
                res[0] = nums[i];
            res[1] ^= (i+1)^nums[i];
        }
        res[1] ^= res[0];
        return res;
    }
Solution 1.  Sort by putting nums[i] at index nums[i]-1
   vector<int> findErrorNums(vector<int>& nums) {
        for(int i=0; i<nums.size(); i++) {
            while(nums[i] != nums[nums[i]-1]) swap(nums[i], nums[nums[i]-1]);
        }
        for(int i=0; i<nums.size(); i++) {
            if(nums[i] != i+1) return {nums[i], i+1};
        }
    }

Solution 2. Use bitset
    vector<int> findErrorNums(vector<int>& nums) {
        bitset<10000> bits(0);
        vector<int> res;
        for(auto n: nums) {
            if(bits.test(n-1)) res.push_back(n);
            else bits.set(n-1);
        }
        for(int i=0; i<bits.size(); i++) {
            if(!bits[i]) {
                res.push_back(i+1);
                break;
            }
        }
        return res;
    }