# 442 - Find All Duplicates in an Array

解法一 - Cyclic Sort

雖然會有多個 element 有 duplicate，我們還是可以先做 cyclic sort，再看哪些 element 跟 index 對應不起來。另外因為只會有最多一個 duplicate，所以直接把跟 index 對應不起來的 element 放到 result 裡就好，而不需要擔心會不會放重複的 element 進 result。

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        // Cyclic sort
        int i = 0, n = nums.size();
        while(i < n) {
            int j = nums[i] - 1;
            if(nums[i] != nums[j]) {
                swap(nums[i], nums[j]);
            }
            else {
                ++i;
            }
        }

        // Get the duplicates
        vector<int> duplicate;

        for(int i = 0; i < n; ++i) {
            if(nums[i] != i + 1) {
                duplicate.push_back(nums[i]);
            }
        }

        return duplicate;
    }
};