c++ - 给定一个从 0 到 n 的整数 vector ，但不是全部包含在内，我如何有效地获取未包含的整数？

Question

给定一个包含从 0 到 n 的整数但未包含所有整数的 vector ，我如何有效地获取未包含的整数？

例如，如果我有一个包含 1 2 3 5 的 vector ，我需要获取包含 0 4 的 vector 。但我需要非常有效地做到这一点。

Answer 1

由于 vector 已经排序，这变得微不足道:

vector<int> v = {1,2,3,5};
vector<int> ret;
v.push_back(n+1); // this is to enforce a limit using less branches in the loop
for(int i = 0, j = 0; i <= n; ++i){
    int present = v[j++];
    while(i < present){
        ret.push_back(i++);
    }
}
return ret;

此外，如果它未排序，您可以对其进行排序并应用上述算法，或者，如果您知道n 的范围，您可以提供额外的内存，您可以创建一个 bool 数组(或位集)并标记对应于您遇到的每个元素的索引 (例如 bitset[v[j++]] = true;)，随后从 0 迭代到 n 并将未标记 bitset 位置的每个元素插入到 vector 中。