笔试题7. LeetCode OJ (7) Find All Numbers Disappeared in an Array

2017-01-13 11:34:05来源:CSDN作者:shenhuan1104人点击

这里写图片描述
题目的意思是:给定一个数组, 1 ≤ a[i] ≤ n,n是数组的长度,在1~n中找到数组中没有出现过的数字。你能做到这一点没有额外的空间和O(N)运行时?您可以假定返回的列表不算作额外空间。

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

第一次遇到这个题目,想来自己先试了下,用两个for循环,这个时间复杂度已经是n的平方了,然而返回的还是一个vector列表,一开始想用vector定义一个数组,可是数组的大小未知,还不知道可以用“ret.push_back(i+1);”的方式,将元素插入到数组ret的尾部。这里的逻辑大家照着代码写一遍就大概能明白其意思。
The basic idea here is to label all appeared numbers in the array. Since we don’t want to introduce extra space and given all numbers are positive(from 1 to n), negate the value in the corresponding position is one choice. Ex, for input like [1, 2, 2], after the first sweep, it becomes [-1, -2, 2]. At position index=2, there is a positive value, which means it corresponding value 3 is not showing.
Hope this simple example gives you some lead :-)
网友说的意思是:这里的基本思想是在数组中标记所有出现的数字.。由于我们不想引进额外的空间,并给出所有的数字是正的(从1到N),对相应的位置的数取反是一个选择。例如,对于输入像[ 1,2,2 ],第一次扫描后,它变成[ - 1,- 2,2 ]。在位置索引= 2,有一个正数,这意味着相应的值3不显示。
希望这个简单的例子给你一些线索。

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台