首页 > 移动平台 > 详细

Find All Numbers Disappeared in an Array

时间:2017-01-12 12:21:52      阅读:41      评论:0      收藏:0      [点我收藏+]

标签:out   and   time   put   find   num   利用   number   arr   

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]

正确的序列就藏在下标里。解法很巧妙,利用负号做标记。
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> temp;
        if (nums.size() == 0)
            return temp;
        unsigned int index = 0;
        for (int i = 0; i < nums.size(); i++)   {
            index = abs(nums[i]) - 1;
            if (nums[index] > 0)
                nums[index] = 0 - nums[index];
        }
        for (int i = 0; i < nums.size(); i ++)  {
            if (nums[i] > 0)
                temp.push_back(i+1);
        }
        return temp;
    }
};

 


Find All Numbers Disappeared in an Array

标签:out   and   time   put   find   num   利用   number   arr   

原文:http://www.cnblogs.com/shawnye/p/6275588.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号