"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, .."

[每日 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

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    122 引用 • 34 回帖
  • array
    45 引用 • 2 回帖
  • Easy
    74 引用 • 10 回帖
感谢    关注    收藏    赞同    反对    举报    分享
回帖    
请输入回帖内容...