# 448 - Find All Numbers Disappeared in an Array

解法一 - Cyclic Sort

雖然這次有多個 duplicate，但我們還是可用 cyclic sort 把對的 element 放到對的 index，剩下不管是多出來的還是 duplicate 的，都會被放在 missing element 的地方。所以只要再走過一次 cyclic sort 完的 array，並把跟 index 不合的所有 element 都放入答案就好。

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

        // Find all missing number 
        vector<int> missed;
        for(int i = 0; i < n; ++i) {
            if(nums[i] != i + 1) {
                missed.push_back(i + 1);
            }
        }

        return missed;
    }
};