大小N的数组有 N-k个不同的数， 范围0-N， 找missing
要求用O(1) space
发信人:
longway2008 (longway2008), 信区: JobHunting
标 题: Re: 问个题：大小N的数组有 N-k个不同的数， 范围0-N， 找miss
发信站: BBS 未名空间站 (Fri Apr 6 07:07:24 2012, 美东)
O(N)时间复杂度
// 大小N的数组有 N-k个不同的数， 范围 0-N-1， 找miss
// 注意：跟楼主题目不同，我假设数字范围从0 -- N-1
vector<int> FindMissingNumbers(vector<int> & a)
{
vector<int> missing;
for (int i=0; i<a.size(); i++)
{
while (a[i]!=a[a[i]])
swap(a[i], a[a[i]]);
if (a[i] != i)
missing.push_back(i);
}
return missing;
}