집합 또는 목록에서 순서대로 누락 된 번호 찾기

Question

std::set 또는 std::list에 일련 번호의 자연수 (1, 2, 3 ..)가 포함 된 경우. 누락 된 번호를 찾기 위해 표준 라이브러리에 기능이 있습니까?

Answer 1

당신은 set_difference 및 사용자 정의 반복자를 사용하여 누락 된 모든 번호를 찾을 수는 :

class seqIter : public std::iterator<std::input_iterator_tag, int> { 
public: 
    seqIter(int n) : num(n) {} 
    seqIter(const seqIter & n) : num(n.num) {} 
    int & operator *() {return num;} 
    seqIter & operator ++() { ++num; return *this; } 
    bool operator !=(const seqIter & n) { return n.num != num; } 
private: 
    int num; 
}; 

int main(int argc, char *argv[]) 
{ 
    int n[] = { 1, 3, 4, 7, 10 }; 
    std::set<int> numbers(n, n + sizeof(n)/sizeof(n[0])); 
    std::set<int> missing; 
    std::set_difference( seqIter(*numbers.begin()+1), seqIter(*numbers.rbegin()), 
          numbers.begin(), numbers.end(), 
          std::insert_iterator<std::set<int> >(missing, missing.begin()) 
         ); 
} 

그것은 아마 하지만 for 루프를 사용하는 것보다 빠르지는 않습니다.

Answer 2

특별히 그 목적을위한 것은 없습니다 (표준 알고리즘은 좀 더 일반화하려고합니다). 그러나 꽤 큰 작품 하나에 std::accumulate을 사용할 수 있습니다.

힌트 : 1..N의 숫자 세트 합계는 (N + 1) * (N/2)입니다.

편집 : 내 대답은 모든 숫자가 있다면 당신이 얻을 수있는 합계에서 가지고있는 숫자의 합계를 뺍니다. 그 차이가 누락 된 숫자가 될 것입니다. 순간

#include <numeric> 
#include <iostream> 

#define elements(x) (sizeof(x)/sizeof(x[0])) 

int main() { 
    int x[] = {8, 4, 3, 5, 1, 2, 7}; 


    int N = elements(x) +1; 

    int projected_sum = (N+1)*(N/2); 
    int actual_sum = std::accumulate(x, x+elements(x), 0); 

    std::cout << "The missing number is: " << projected_sum - actual_sum << "\n"; 
    return 0; 
} 

,이 세트가 요소의 홀수가있는 경우 발생하는 등 몇 가지 사소한 세부 사항을 무시하지만 일반적인 생각을 표시해야합니다. 필자는 또한 목록 대신에 배열을 사용하여 간단하게 초기화 할 수 있습니다. 목록에서 (합리적으로) 지원할 수없는 임의 액세스와 같은 것을 사용하지 않았습니다. 이것은 선형 복잡성을 가지고 있으며 샘플 입력에서 볼 수 있듯이 입력을 정렬 할 필요가 없습니다.

편집 2 : 의도가 입력이 정렬 된 순서 인 경우 작업을 조금 다르게 처리 할 것입니다. 이전 버전보다 정확히 하나는 아닌 항목을 찾아 보겠습니다.

Answer 3

std::mismatch() 일련의 자연수를 사용할 수 있습니다. 공간을 절약하기 위해, 나는 여기 boost::counting_iterator 작품을 궁금해 생각 :

는

#include <iostream> 
#include <list> 
#include <boost/iterator/counting_iterator.hpp> 
int main() 
{ 
    std::list<int> l = {1,2,3,4,6,7,8,9}; 
    auto i = mismatch(l.begin(), l.end(), boost::counting_iterator<int>(1)); 
    if(i.first==l.end()) 
      std::cout << "no missing numbers\n"; 
    else 
      std::cout << "the first missing number is " << *i.second << '\n'; 

} 

테스트 실행은 :

~ $ g++ -std=c++0x -pedantic -Wall -Wextra -o test test.cc 
~ $ ./test 
the first missing number is 5