使用STL算法查找集合中的前两个非相邻元素 [英] Find First Two Non-Adjacent Elements in a set Using an STL Algorithm
问题描述
所以我真的为此感到挣扎,即使现在我对自己的解决方案也不满意.
So I really struggled with this and even now I am not happy with my solution.
我有一个set
,至少包含0,并且可能包含其他正数int
.我需要在set
中找到第一个正数 not .
I have a set
that at least contains 0, and may contain other positive int
s. I need to find the first positive number not in the set
.
因此,编写标准的while
循环来完成此操作很容易.
So writing a standard while
-loop to accomplish this is easy.
i = foo.begin();
while (i != prev(foo.end()) && *i + 1 == *next(i)){
++i;
}
cout << "First number that cannot be formed " << *i + 1 << endl;
但是当我尝试编写该循环的STL算法版本时,会得到类似该循环的错误消息:
But when I try to write an STL algorithm version of the loop I get something that fails like this loop:
auto i = foo.begin();
while (++i != prev(foo.end()) && *prev(i) + 1 == *i);
cout << "First number that cannot be formed " << *prev(i) + 1 << endl;
在以下情况下,这两个循环均正确产生 3 :
Both of these loops correctly yield 3 in the case of:
set<int> foo{0, 1, 2, 4};
但是在这种情况下,第二个循环错误地产生了3而不是 4 :
But the second loop incorrectly yields 3 instead of 4 in this case:
set<int> foo{0, 1, 2, 3};
如何使用STL算法编写此代码并完成第一个循环的行为?
看到一些答案后,我想增加难度.我真正想要的是不需要临时变量并且可以放在cout
语句中的东西.
After seeing some of the answers, I'd like to increase the difficulty. What I really want is something that doesn't require temporary variables and can be placed in a cout
statement.
推荐答案
循环的问题是您过早停止了一个元素.这有效:
The problem with your loop is that you stop one element too early. This works:
while (++i != foo.end() && *prev(i) + 1 == *i);
与第一个循环的区别是条件*prev(i) + 1 == *i)
而不是*i + 1 == *next(i)
;您检查的范围必须相应地移动.
The difference to the first loop is the condition *prev(i) + 1 == *i)
instead of *i + 1 == *next(i)
; the range you check has to shift accordingly.
您也可以使用std::adjacent_find
:
auto i = std::adjacent_find(begin(s), end(s), [](int i, int j) { return i + 1 != j; });
if(i == s.end()) {
std::cout << *s.rbegin() + 1 << std::endl;
} else {
std::cout << *i + 1 << std::endl;
}
对编辑的响应:使其完全内联的一种方法是
Response to the edit: A way to make it prettily inlineable is
std::cout << std::accumulate(begin(s), end(s), 0,
[](int last, int x) {
return last + 1 == x ? x : last;
}) + 1 << '\n';
...但是效率较低,因为它在发现间隙时不会短路.造成短路的另一种方法是
...but this is less efficient because it does not short-circuit when it finds a gap. Another way that does short-circuit is
std::cout << *std::mismatch(begin (s),
prev(end (s)),
next(begin(s)),
[](int lhs, int rhs) {
return lhs + 1 == rhs;
}).first + 1 << '\n';
这篇关于使用STL算法查找集合中的前两个非相邻元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!