给定一个包含从 0 到 n 的整数但未包含所有整数的 vector ,我如何有效地获取未包含的整数?
例如,如果我有一个包含 1 2 3 5 的 vector ,我需要获取包含 0 4 的 vector 。 但我需要非常有效地做到这一点。
最佳答案
由于 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 中。
关于c++ - 给定一个从 0 到 n 的整数 vector ,但不是全部包含在内,我如何有效地获取未包含的整数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17409612/