LeetCode/solutions/448. Find All Numbers Disappeared in an Array.md

448. Find All Numbers Disappeared in an Array

思路

题目要求线性的时间复杂度且不适用额外的空间，所以最基本的先排序再判断就不行了。

思路一

依然是考虑将数组排序。由于数组元素的特殊性，其实每一个数在排序后应该在的位置是能立即确定的，例如2应该在nums[1], 5应该在nums[4]。
所以我们从前往后遍历数组，不断循环将元素交换到应该在的位置，直到无法交换。
无法交换的情况有二:

• nums[i] == i+1, 即已经在应该在的位置;
• nums[nums[i]-1] == nums[i], 即元素值等于期望交换的位置的元素值

仔细观察其实可以发现情况2包含了情况1, 所以代码中只写情况2就行了。
如果满足交换条件，则每次都会使一个元素处在正确位置，因为总共有n个元素，所以至多需要n-1次交换, 所以时间复杂度O(n)。

思路二

我们只需要知道没有出现哪些元素，即第一次遍历的时候对已经出现的元素作个二值标记，第二次遍历时候寻找没有标记的位置即可。
怎么进行标记呢？容易想到的就是开辟一个大小为n的标记数组(或者用map)，但是有没有不用额外空间的办法呢？
由于nums就是一个大小为n的数组，所以我们考虑在不覆盖掉原有的元素(即第二次遍历时能够得到该位置原元素值)的基础上用nums作为标记数组。
为了第二次遍历时能够得到该位置原元素值，有多种思路：

• 由于元素都是1~n的，所以如果对某元素加上n+1, 第二次遍历时对n+1取模即可得到原元素；
• 由于元素都是大于0的，所以使某元素为对应的负数也能达到目的。

因为加上n+1可能存在溢出的问题，所以我们采取第二种思路，即从前往后遍历， 将位置为nums[i]-1的元素变为对应的负数(即nums[abs(nums[i])-1] = -abs(nums[abs(nums[i])-1]))。
第二次遍历时，若位置i上的数为正数，则缺失了数i+1。
两次遍历，所以时间复杂度O(n)

C++

思路一

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int tmp, i = 0;
        while( i < nums.size()){
            if(nums[nums[i]-1] == nums[i]){ // 无法交换
                i++;
                continue;
            }
            // 交换
            tmp = nums[nums[i]-1];
            nums[nums[i]-1] = nums[i];
            nums[i] = tmp;
        }
        
        vector<int>result;
        for(int i = 0; i < nums.size(); i++)
            if(nums[i] != (i + 1))
                result.push_back(i+1);
 
        return result;        
    }
};

思路二

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++)
            nums[abs(nums[i]) - 1] = -1 * abs(nums[abs(nums[i]) - 1]);
        
        vector<int>result;
        for(int i = 0; i < nums.size(); i++)
            if(nums[i] > 0)
                result.push_back(i+1);
        
        return result;
    }
};