[每日 LeetCode] 448. Find All Numbers Disappeared in an Array

Description:

Given an array of integers where 1 ≤ a[i] ≤ n ( n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]
​

思路：本题要求找出数组中没有出现过的 1-n（n 为数组长度）之间的数字。定义一个长度为 n 的数组 temp，全都初始化为 0。然后遍历给出的数组，令 temp[nums[i]-1]=-1。最后遍历数组 temp，那些值为 0 的数的位置加上 1 就是所要求的没有出现的数。

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

运行时间：120ms
运行内存：16.4M