442. Find All Duplicates in an Array ----------M ~~~~~~~

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output: 

[2,3] 

A:

首先是用set的。

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        unordered_set<int> S;
        vector<int> res;
        for(auto k : nums){
            if(S.find(k) == S.end()){
                S.insert(k);
            }else{
                res.push_back(k);
            }
        }
        return res;
    }
};

然后利用1 ≤ a[i] ≤ n (n = size of array),   就是换来换去。 搞到 no extra space and O(1) time.

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < 0 || nums[i] == i + 1)
                continue;
            // if taget place already have the value
            if (nums[i] == nums[nums[i] - 1]) { 
                res.push_back(nums[i]);
                nums[i] = -1;
            }else {
                swap(&nums[i], &nums[nums[i] - 1]);
                i--;
            }
        }
        return res;
    }
private:
    void swap(int* a, int* b) {
        *a = *a ^ *b;
        *b = *a ^ *b;
        *a = *a ^ *b;
    }
};

~~~~~~swap 两个数，可以用指针，也可以用  引用。 

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        // since 1 ≤ a[i] ≤ n (n = size of array), we place value k at nums[k-1]
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < 0 || nums[i] == i + 1)
                continue;
            // if taget place already have the value
            if (nums[i] == nums[nums[i] - 1]) { // if target value already ocuppied
                res.push_back(nums[i]);
                nums[i] = -1;
            }
            else {
                 swap2(nums[i], nums[nums[i] - 1]);
                i--;
            }
        }
        return res;
    }
private:
    void swap2(int & a, int & b) {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }
};