确定第一个可用号码

Question

所以我要做的是确定不在向量中的第一个值。 例如，如果我有一个这样的向量

std::vector<unsigned int> s = {10, 9, 7, 1, 3};

我想要 2。

我该怎么做？

Answer 1

蛮力：使用循环

for (int number=1; number< s.size(); ++number) {
bool found = false;
for (int i=0;i < s.size(); ++i) {
if (s[i] == number) found = true;
}
if (!found) return number;
}

这具有二次复杂度，可能与 5 个元素无关，但它也不是很好的代码。

减少暴力：排序

对数字进行排序后，您只需从头开始，直到缺少数字：

std::sort(s.begin(),s.end());
if (s[0] != 1) return 1;
int number = 1;
for (int i=1;i<s.size();++i) {
if (s[i] != number && s[i] != number+1) return number+1;
number = s[i];
}    

更好

做某事的最佳方法是不做。数字从何而来？你如何填充矢量？在填充数组时，您不能已经确定第一个缺失的数字吗？

附言

上面的代码假设向量不为空，并且只包含数字>= 1。

Answer 2

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main()
{
vector<unsigned int> s = {10, 9, 7, 1, 3};
set<unsigned int> given_numbers;
for(auto i:s)
given_numbers.insert(i);
int i=1;
while(true){
if(!given_numbers.count(i)){
cout<<i<<endl;
break;
}
i++;
}
return 0;
}