Найти пропущенный номер в последовательности в наборе или списке - PullRequest
Новая
       25

Найти пропущенный номер в последовательности в наборе или списке

1 голос
/ 16 июня 2010

Если std::set или std::list содержит последовательность натуральных чисел (1, 2, 3 ..).будет ли в стандартной библиотеке функция для поиска пропущенного числа?

Ответы [ 3 ]

6 голосов
/ 16 июня 2010

Вы можете 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
4 голосов
/ 16 июня 2010

Вы можете найти все пропущенные числа, используя 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.

3 голосов
/ 16 июня 2010

Нет специально для этой цели (стандартные алгоритмы пытаются быть более обобщенными). Однако вы могли бы использовать 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;
}

На данный момент, это игнорирует несколько незначительных деталей, например, что происходит, если набор имеет нечетное количество элементов, но должен показывать общую идею. Я также использовал массив вместо списка, просто для простоты инициализации. Я не использовал ничего похожего на произвольный доступ, который не может (разумно) поддерживать список. Это имеет линейную сложность и, как видно из примера ввода, не требует сортировки ввода.

Edit2: если намерение состоит в том, что входные данные расположены в отсортированном порядке, я, вероятно, выполнил бы работу немного по-другому: просто пролистайте и найдите элемент, который точно не больше, чем его предшественник.

...