Unsorted Array Problem Summary

Unsorted Array，如果要求solution需要O(n) complexity，则往往需要hash table来辅助。而如果further follow up，需要O(1) space, 则需要借助原数组，来移动，或者改变元素。

Find All Numbers Disappeared in an Array (Leetcode 448)
https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

用Hash Table，直接明了。

vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> ret;
        if(nums.empty()) return ret;
        unordered_map<int, int> mp;
        for(int i=0; i<nums.size(); i++){
            mp[nums[i]]++;
        }
        for(int i=1; i<=nums.size(); i++){
            if(!mp.count(i)) ret.push_back(i);
        }
        return ret;
    }

如果不用Hash Table，则需要对元素进行改变。而且一般需要扫两遍。这时，要抓住一些数组元素的特点。这道题的特点是所有元素都是大于0，而且元素都是在1到n之间，n为数组size。这样我们可以没loop到一个数，便将以该数为index的数组元素乘以-1。最后看谁大于0.

vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> ret;
        if(nums.empty()) return ret;
        for(int i=0; i<nums.size(); i++){
            int idx = abs(nums[i]) - 1;
            if(nums[idx] > 0) nums[idx] = -nums[idx];
        }
        for(int i=0; i<nums.size(); i++){
            if(nums[i] > 0) ret.push_back(i+1);
        }
        return ret;
    }

Find All Duplicates in an Array (Leetcode 442)
https://leetcode.com/problems/find-all-duplicates-in-an-array/

与上一题解法差不多，记住要取绝对值

 vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ret;
        if(nums.empty()) return ret;
        for(int i=0; i<nums.size(); i++){
            int idx = abs(nums[i])-1;
            if(nums[idx] > 0) nums[idx] = -nums[idx];
            else ret.push_back(idx+1);
        }
        return ret;
    }

First Missing Positive (Leetcode 41):
https://leetcode.com/problems/first-missing-positive/

这道题用hash table的方法也比较明确。先把数组都放到hash table里，然后从1往上找，看哪个数最先没有被找到。

而如果需要constant space, 就还是要求改变数组位置。这里网上的解法是尽量把 1到n之间的数，放到其合适的位置上去(nums[i-1])，即将nums[i], 放到nums[nums[i] - 1]上面去。
最后再从1往上找，看哪个数不在其位置上。放置的方法很巧妙，需要swap。

int firstMissingPositive(vector<int>& nums) {
        if(nums.empty()) return 1;
        int n = nums.size();
        int i = 0; 
        while(i < n){
            if(nums[i] > 0 && nums[i] <= n && nums[i] != i+1 && nums[i] != nums[nums[i]-1]){
                int idx = nums[i]-1;
                swap(nums[i], nums[idx]);
            }
            else i++;
        }
        for(int i=1; i<=n; i++){
            if(nums[i-1] != i) return i;
        }
        return n+1;
    }