c++ - 确定第一个可用号码

Question

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

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];
 }    

更好

做某事的最佳方式就是不去做。这些数字来自哪里？你如何填充 vector ？在弹出数组时，您不能确定第一个缺失的数字吗？

附言

上面的代码假定 vector 不为空并且只包含数字>= 1。