Нахождение разрывов в последовательности чисел
количество пробелов / табуляций в начале строки указывает структуру, например какой код выполняется как часть операторов if и циклов for. поэтому вам нужно быть более систематичным с форматированием вашего кода…
текстовые редакторы, предназначенные для редактирования кода, как правило, помогают в этом.
Кроме того, if k == 27: выглядит неопределенным, то есть что вы хотите сделать, если пользователь нажал клавишу выхода?
8 ответов
Проверенное использование ответа <для сравнения.! = намного более просто:
int find_gap(std::vector<int> vec) {
std::sort(vec.begin(), vec.end());
int next = 1;
for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
if (*it != next) return next;
++next;
}
return next;
}
find_gap(1,2,4,5) = 3
find_gap(2) = 1
find_gap(1,2,3) = 4
Я не передаю ссылку на вектор так как a) он сказал, что время не имеет значения и b) таким образом, я не изменяю порядок исходного вектора.
Сортировка списка и затем выполнение линейного поиска кажутся простым решением. В зависимости от ожидаемого состава списков Вы могли использовать алгоритм сортировки менее общей цели, и если Вы реализуете вид сами, Вы могли бы отслеживать данные во время вида, который мог бы использоваться, чтобы убыстриться (или устранить полностью) поисковый шаг. Я не думаю, что существует любое особенно изящное решение этой проблемы
Стандартный алгоритм, который Вы ищете, является станд.:: adjacent_find.
Вот решение, которое также использует лямбду для создания предиката чистым:
int first_gap( std::vector<int> vec )
{
// Handle the special case of an empty vector. Return 1.
if( vec.empty() )
return 1;
// Sort the vector
std::sort( vec.begin(), vec.end() );
// Find the first adjacent pair that differ by more than 1.
auto i = std::adjacent_find( vec.begin(), vec.end(), [](int l, int r){return l+1<r;} );
// Handle the special case of no gaps. Return the last value + 1.
if ( i == vec.end() )
--i;
return 1 + *i;
}
На самом деле, если Вы делаете пузырьковую сортировку (Вы знаете... тот, который они преподают Вам сначала и затем говорят Вам никогда не использовать снова...), Вы сможете определить первый разрыв рано в процессе сортировки, таким образом, можно будет остановиться там. Это должно дать Вам самое быстрое полное время.
Вы могли выделить немного вектора (той же длины как входной вектор), инициализировать его для обнуления, затем отметить все индексы, которые происходят (обратите внимание, что числа, больше, чем длина, могут быть проигнорированы). Затем возвратите первый неотмеченный индекс (или длина, если все индексы отмечены, который только происходит, если все индексы происходят точно однажды во входном векторе).
Это должно быть асимптотически быстрее, чем вид и поиск. Это будет использовать больше памяти, чем сортировка, если Вам разрешат уничтожить оригинал, но меньше памяти, чем сортировка, если необходимо сохранить оригинал.
Sort-n-search:
std::sort(vec.begin(), vec.end());
int lowest = 1;
for(size_t ii = 1; ii < vec.size(); ++ii)
{
if (vec[ii - 1] + 1 < vec[ii])
{
lowest = (vec[ii - 1] + 1);
break;
}
}
/* 1, 2, ..., N case */
if (lowest == vec[0]) lowest = (*vec.back()) + 1;
Итераторы могли использоваться с в качестве ясного намерения, как продемонстрировано в @joe_mucchiello (редактор: лучше) ответ.
Вы могли пойти с чем-то как....
struct InSequence
{
int _current; bool insequence;
InSequence() : _current(1), insequence(true){}
bool operator()(int x) {
insequence = insequence ? (x == _current) : false;
_current++;
return insequence;
}
};
int first_not_in_sequence(std::vector<int>& v)
{
std::sort(v.begin(), v.end());
return 1+std::count_if(v.begin(), v.end(),InSequence());
}
Хорошо, вот мои 2 цента. Предположите, что у Вас есть вектор длины N.
- Если N <=2 можно проверить непосредственно
- Во-первых, используйте min_element, чтобы получить самый маленький элемент, помнить это как emin
- Назовите nth_element, чтобы получить элемент в N/2, назвать его ehalf
- Если ehalf! = emin+N/2 налево существует разрыв, примените этот метод рекурсивно там путем вызова nth_element на целом массиве, но просьбы элемент N/4. Иначе рекурсивно вызовите право, просящее элемент 3*N/4.
Это должно быть немного лучше, чем сортировка абсолютно впереди.