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

  |   0 评论   |   573 浏览

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

评论

发表评论