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

Question

给定一个包含从 0 到 n 的整数但未全部包含在内的向量，我如何有效地获取未包含的整数？

例如，如果我有一个包含 1 2 3 5 的向量，我需要获取包含 0 4 的向量。但我需要非常高效地完成它。

Answer 1

由于向量已经排序，这变得微不足道：

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，并且您可以负担额外的内存，则可以创建一个布尔数组（或位集）并标记与您遇到的每个元素相对应的索引，随后从to(e.g. bitset[v[j++]] = true;)迭代并将其位集位置尚未标记的每个元素插入到您的向量中。0n

Answer 2

基本上，这里提出的想法是，如果我们可以假设没有重复值的排序输入，我们会事先知道缺失项目的数量。然后可以预先分配足够的空间来预先保存缺失值（不需要以后动态分配）。然后我们还可以在找到所有缺失值时利用可能的捷径。

如果输入向量未排序或包含重复值，则可以使用建立此前提条件的包装函数。

#include <iostream>
#include <set>
#include <vector>

inline std::vector<int> find_missing(std::vector<int> const & input) {
    // assuming non-empty, sorted input, no duplicates
    // number of items missing
    int n_missing = input.back() - input.size() + 1;
    // pre-allocate enough memory for missing values
    std::vector<int> result(n_missing);
    // iterate input vector with shortcut if all missing values were found
    auto input_it = input.begin();
    auto result_it = result.begin();
    for (int i = 0; result_it != result.end() && input_it != input.end(); ++i) {
        if (i < *input_it) (*result_it++) = i;
        else ++input_it;
    }
    return result;
}

// use this if the input vector is not sorted/unique
inline std::vector<int> find_missing_unordered(std::vector<int> const & input) {
    std::set<int> values(input.begin(), input.end());
    return find_missing(std::vector<int>(values.begin(), values.end()));
}

int main() {
    std::vector<int> input = {1,2,3,5,5,5,7};
    std::vector<int> result = find_missing_unordered(input);
    for (int i : result)
        std::cout << i << " ";
    std::cout << "\n";
}

输出是：

$ g++ test.cc -std=c++11 && ./a.out 
0 4 6