如何在 C++ 中输出集合中的缺失数字？

Question

如果我在 C++ 中有一个集合，它包含从 0 到 n 的数字。我想找出从 1 到 n 缺少的数字并输出，如果缺少 none，则输出数字 (n+1).

例如，如果集合包含0 1 2 3 4 5 6 7，那么它应该输出8 如果它包含 0 1 3 4 5 6，那么它应该输出 2。我为此编写了以下代码，但它似乎总是输出 0。不知道是什么问题

set<int>::iterator i = myset.begin();
set<int>::iterator j = i++;
while (1)
{
    if ( *(j) != *(i)+1 )
    {
        cout<<*(j)<<"\n";
        break;
    }
    else
    {
        i++;
        j++;
    }
}

有什么问题？谢谢！

Answer 1

问题是你在前进i:

set<int>::iterator i = myset.begin(); // <-- i points to first element
set<int>::iterator j = i++;           // <-- j points to first element
                                      //     i points to second!
while (1)
{                                     // so if our set starts with {0, 1, ...}
    if ( *(j) != *(i)+1 )             // then *j == 0, *i == 1, *i + 1 == 2, so this
                                      // inequality holds

你的意思是让 j 成为 next 之后的迭代器 i:

std::set<int>::iterator i = myset.begin(), j = myset.begin();
std::advance(j, 1);

对于 C++11，还有 std::next():

auto i = myset.begin();
auto j = std::next(i, 1);

或者，或者，只是反转你的构造：

std::set<int>::iterator j = myset.begin();
std::set<int>::iterator i = j++; // now i is the first element, j is the second

或者，最后，您真的只需要一个迭代器：

int expected = 0;
for (std::set<int>::iterator it = myset.begin(); it != myset.end(); 
     ++it, ++expected)
{
    if (*it != expected) {
        std::cout << "Missing " << expected << std::endl;
        break;
    }
}

Answer 2

最简单的东西：使用 set 的 count() 函数来检查集合中是否存在元素。

count() 接受一个整数参数：要检查其在集合中是否存在的数字。如果元素存在于集合中，count() returns 一个非零值，否则它 returns 0.

例如：

#include <iostream>
#include <set>
using namespace std;
int main()
{
    set<int> s;
    //I insert 0 - 4 in the set.
    for(int i=0;i < 5; ++i)
        s.insert(i);
    //Let 10 be the 'n'.
    for(int i = 0; i < 10; ++i)
    {
        //If i is NOT present in the set, the below condition will be true.
        if (!s.count(i)) 
            cout<<i<<" is missing!\n";
    }
}

Answer 3

一个问题是，如果集合是密集，这是未定义的行为。另一个是你总是输出集合中的一个元素（*j，其中 j 是集合中的迭代器）；根据您的描述，您要输出的是一个值不在集合中。

有几种方法可以处理这个问题。最简单的可能是只是维护一个变量 expected，用 0 和初始化每次递增。类似于以下内容。

int
firstAvailable( std::set<int> const& allocated )
{
    int expected = 0;
    for ( auto current = allocated.begin(), end = allocated.end();
            current != end && *current == expected;
            ++ current ) {
        ++ expected;
    }
    return expected;
}

如果你不想 return 0 如果列表不为空，但以一些其他值，用第一个元素初始化 expected 设置（或者如果设置为空，则使用您想要的任何内容 return）。

编辑：

当然，其他算法可能会更好。对于这种事情，我通常使用位图。

Answer 4

你原来代码的问题已经在其他答案中指出了。您在分配 j 时正在修改 i。您可以通过将迭代器初始化为：

来解决此问题

set<int>::iterator i = myset.begin();
set<int>::iterator j = i;
j++;

一个更优雅的解决方案是利用 n 以内所有值的总和为 n * (n + 1) / 2 这一事实。您可以计算实际值的总和，并从总和中减去它以获得缺失值：

int findMissing(const std::set<int>& valSet) {
    int valCount = valSet.size();
    int allSum = (valCount * (valCount + 1)) >> 1;
    int valSum = std::accumulate(valSet.begin(), valSet.end(), 0);
    return allSum - valSum;
}

这种方法的最大优点是它不依赖于使用迭代器按排序顺序提供值的容器。您可以使用相同的解决方案，例如在未排序的 std::vector.

使用这种方法时要注意的一个危险是溢出。对于 32 位整数，它将溢出大约 2^16 个值。如果它溢出，它实际上可能仍然有效，特别是如果您使用 unsigned 而不是 int，但我没有确认这一点。

有一种类似的方法，使用所有值的异或而不是求和，它没有溢出问题。

如何在 C++ 中输出集合中的缺失数字？

How to output a missing number in set in c++?

c++

algorithm