否定数字列表 [英] Negating a List Of Numbers
问题描述
我正在寻找一种有效的方法来创建一个
数字列表的对话。
例如，假设我有这个数字列表：
100
200
300
我想生成1到999之间所有数字的列表
不包括此列表中的数字。
欢迎任何建议。
问候，
Eduardo
Hi,
I''m looking for an efficient way to create the oposite of a
list of numbers.
For example, suppose I have this list of numbers:
100
200
300
I want to generate a list of all numbers between 1 and 999 that
exclude the numbers in this list.
Any suggestions are welcome.
Regards,
Eduardo
推荐答案
将数字列表存储在向量中，构建一个谓词函数，
包含数字列表，如果比较某些内容则返回true
到这些数字之一，创建一个空向量，然后在向量上执行
remove_copy_if，其中数字为目标空
向量。您的（一次）空向量现在应该包含列表中的所有值而不是
。
Store the list of numbers in a vector, build a predicate function which
contains the list of numbers and returns true if something is compared
to one of these numbers, create an empty vector , then perform
remove_copy_if on the vector with the numbers with as target the empty
vector. Your (once) empty vector should now contain all the values not
on the list.
" Eduardo Bezerra" < ED **** @ gmail.com>在消息中写道
news：58 ************************** @ posting.google.c om ...
"Eduardo Bezerra" <ed****@gmail.com> wrote in message
news:58**************************@posting.google.c om...
我正在寻找一种有效的方法来创建一个数字列表的对话。
例如，假设我有这个数字列表：
100
我想生成1到999之间所有数字的列表
排除这个列表中的数字。
I''m looking for an efficient way to create the oposite of a
list of numbers.
For example, suppose I have this list of numbers:
100
200
300
I want to generate a list of all numbers between 1 and 999 that
exclude the numbers in this list.
我认为如果不执行大量操作就不可能做到这一点
与域名成比例（这里[1,999]）。我的理由是，如果n是域的大小，而m是列表中元素的数量，那么构建结果必须至少采用nm操作（因为它具有很多元素，并且检查输入必须进行m次操作（因为你需要检查输入的每个元素至少一次才能知道
它是什么）。所以你必须至少执行O（n）操作。
那么，问题是你需要多接近O（n）。有一种简单的方法来解决O（n + log（m））操作中的问题：对输入进行排序，然后
沿着以下行写一个循环：
vector< int> :: const_iterator it = input.begin（）;
for（int i = 1; i< = 999; ++ i）{
if（it！= input.end（）&& i == * it）
++ it;
其他
output.push_back（i）;
}
所以我的问题是：这是解决方案吗？够好了？如果没有，那么什么是不好的？b $ b足够的它和你认为足够好的东西？
I think it''s impossible to do this without executing a number of operations
proportional to the domain (here [1,999]). My reasoning is that if n is the
size of the domain and m is the number of elements in the list, merely
building the result must take at least n-m operations (because it has that
many elements) and checking the input must take m operations (because you
have to examine every element of the input at least once in order to know
what it is). So you must execute at least O(n) operations.
The question, then, is how close to O(n) you need to be. There is an easy
way to solve the problem in O(n+log(m)) operations: Sort the input, then
write a loop along the following lines:
vector<int>::const_iterator it = input.begin();
for (int i = 1; i <= 999; ++i) {
if (it != input.end() && i == *it)
++it;
else
output.push_back(i);
}
So my question is: Is this solution good enough? If not, what''s not good
enough about it and what would you consider good enough?
我认为使用套装将是如何解决这个问题。
的最佳方式，就像我看到的那样：
------------------- -----------------
set< int>排除，结果;
//使用要排除的整数列表填充排除集
for（int i = 0; i< 1000; i ++）
if（！exclude.count（i））
result.insert（i）;
--- ---------------------------------
然后''疯狂的方式，实际上提供了非常接近的
零性能优势（可能更糟糕，取决于你的
编译器），但我觉得发帖是因为我认为它'太酷了：
------------------------------------
/ *你不应该*实际上*使用这段代码* /
class int_it：public iterator< input_iterator_tag，int> {
public：
int i;
int_it（int c）：i（c）{};
inline void operator ++（）{i ++; };
inline int operator *（）{return i; };
inline bool operator！=（const int_it& second）{return second.i！= i; };
};
int main（）
{
set< int> exclude，result;
int_it start_i（1），end_i（1000）;
//使用要排除的整数列表填充排除集
set_difference（start_i，end_i，exclude.begin（），exclude.end（），
inserter< int>（result，result.begin（） ））;
}
------------------------------ ------
我认为第一种方式就是尽可能高效，假设
你不知道清单事先排除了数字。
如果你事先知道这些数字并且非常关心
一点点的效率（我说的很轻微，假设你是
没有使用多兆字节集），那么你可以使用程序
生成一个完美的哈希函数来生成数学
公式，以确定是否应该包括一个数字，但是'
真的分裂了。
I think using sets would be the way to go about this. The best way to
go about it, as I see, is this:
------------------------------------
set<int> exclude, result;
//Fill the exclude set with the list of integers you want to exclude
for(int i=0; i<1000; i++)
if (!exclude.count(i))
result.insert(i);
------------------------------------
and then there''s the insane way, that actually provides very close to
zero performance benefits (maybe even worse depending on your
compiler), but I feel like posting cause I think it''s cool:
------------------------------------
/* You shouldn''t *actually* use this code */
class int_it : public iterator<input_iterator_tag, int> {
public:
int i;
int_it(int c):i(c) {};
inline void operator++() { i++; };
inline int operator*() { return i; };
inline bool operator!=(const int_it &second) { return second.i != i; };
};
int main()
{
set<int> exclude, result;
int_it start_i(1), end_i(1000);
//Fill the exclude set with the list of integers you want to exclude
set_difference(start_i, end_i, exclude.begin(), exclude.end(),
inserter<int>(result, result.begin()));
}
------------------------------------
I think the first way is about as efficient as you can get, assuming
you don''t know the list of excluded numbers beforehand.
If you do know the numbers beforehand and really care about the
slightest bit of efficiency (and I''m talking slight, assuming you''re
not working with multi-megabyte sets), then you could use the programs
which generate a perfect hash function to generate a mathematical
formula to determine if a number should be included or not, but that''s
really splitting hairs.
这篇关于否定数字列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
