442. Find All Duplicates in an Array

[namespace-io]

交换一下

class Solution {
public:
    vector<int> findDuplicates(vector<int>& a) {
        int n = a.size();
        for(int i = 0; i < n; i++){
            while(i != a[i]-1 && a[a[i]-1] != a[i]) swap(a[a[i]-1], a[i]);
        }
        
        vector<int> ret;
        for(int i = 0; i < n; i++){
            if(i != a[i] - 1) ret.push_back(a[i]);
        }
        
        return ret;
    }
};

将遇到a[idx]就翻转，如果为负，说明之前有重复的。

class Solution {
public:
    vector<int> findDuplicates(vector<int>& a) {
        int n = a.size();
        vector<int> ret;
        for(int i = 0; i < n; i++){
            int idx = abs(a[i]) - 1;
            if(a[idx] < 0) ret.push_back(idx + 1);
            a[idx] = -a[idx];
        }

        return ret;
    }
};