如何在C++中輸出缺少的數字集？

如果我在C++中有一個集合，它包含從0到n的數字。我希望找出從1到n丟失的數字並輸出，如果沒有丟失，則輸出數字（n + 1）。如何在C++中輸出缺少的數字集？

例如，如果該集合包含，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++; 
    } 
}

什麼問題？謝謝！

來源

2015-01-10 John Yad

的問題是，你正在推進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是下一個迭代後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; 
    } 
}

來源

2015-01-10 17:09:28 Barry

很好的解釋，但爲了處理缺失數字在集合末尾的情況，這是我給出的第一個示例，該如何處理？ –

對於初學者來說，問題是他正在訪問超出數組的末尾。使用兩個迭代器（加上結束迭代器）編寫正確的代碼是很有可能的，儘管恕我直言，這不是最好的解決方案。但在任何情況下，您都必須確保所有對該集合的訪問都在限制範圍內。 –

換句話說，您的上一個版本是最好的方法。但爲什麼會把問題與'break'混淆？只需將條件添加到'for'中的條件中，並且當您離開循環時，無論「預期」是什麼，那就是他正在尋找的值。 –

最簡單的東西：使用count()的set函數來檢查是否一個元素是否存在或不存在。

count()需要一個整數參數：要檢查集合中存在的數字。如果元素存在於集合中，則count()返回非零值，否則返回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"; 
    } 
}

來源

2015-01-10 17:16:14 shauryachats

一個問題是，您訪問超出設定結束時，如果設定爲密集，這是不確定的行爲。另一個是你總是輸出集合中的一個元素（*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; 
}

如果你不想返回0，如果列表不爲空，但與一些其他的值開始，與組的第一個元素初始化expected（或任何你想返回如果該集合是空的）。

編輯：

當然，其他算法可能會更好。對於這種事情，我通常使用一個位圖。

來源

2015-01-10 17:41:48

您的原始代碼問題已在其他答案中指出。您正在修改i，同時指定j。您可以通過初始化迭代器爲解決這個問題：

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，但我沒有證實。

有一種類似的方法，使用所有值的XOR而不是總和，這沒有溢出問題。

來源

2015-01-11 07:47:56

如何在C++中輸出缺少的數字集？

回答

相關問題