Найдите «дыру» в списке чисел

14

Какой самый быстрый способ найти первое (наименьшее) целое число, которого нет в данном списке несортированных целых чисел (и которое больше, чем наименьшее значение в списке)?

Мой примитивный подход - сортировка и пошаговый просмотр списка, есть ли лучший способ?

Фабиан Цейндль
источник
6
@Jodrell Я думаю, что сортировка бесконечной прогрессии будет трудной ;-)
maple_shaft
3
@maple_shaft согласился, может занять некоторое время.
Джодрелл
4
Как вы определяете сначала для несортированного списка?
Джодрелл
1
Я только что понял, что это, вероятно, принадлежит StackOverflow, так как это не является концептуальной проблемой.
JasonTrue
2
@JasonTrue из FAQ, If you have a question about… •algorithm and data structure conceptsэто по теме ИМХО.
maple_shaft

Ответы:

29

Предполагая, что вы имеете в виду «целое число», когда говорите «число», вы можете использовать битовый вектор размером 2 ^ n, где n - количество элементов (скажем, ваш диапазон включает целые числа от 1 до 256, тогда вы можете использовать 256- бит или 32 байта, битвектор). Когда вы встретите целое число в позиции n вашего диапазона, установите n-й бит.

Завершив перечисление набора целых чисел, вы перебираете биты в своем битовом векторе, ища позицию любых битов, установленных в 0. Теперь они соответствуют позиции n вашего отсутствующего целого (ых) числа.

Это O (2 * N), поэтому O (N) и, вероятно, более эффективно использует память, чем сортировка всего списка.

JasonTrue
источник
6
Ну, как прямое сравнение, если бы у вас были все 32-разрядные целые числа без знака, кроме 1, вы могли бы решить проблему отсутствующего целого числа примерно в половине гигабайта памяти. Если вы сортируете вместо этого, вам придется использовать более 8 гигабайт памяти. И сортировка, за исключением особых случаев, подобных этому (ваш список сортируется, когда у вас есть битовый вектор), почти всегда n log n или хуже, поэтому, за исключением случаев, когда константа перевешивает сложность по стоимости, выигрывает линейный подход.
JasonTrue
1
Что если вы не знаете диапазон априори?
Blrfl
2
Если у вас целочисленный тип данных Blrfl, вы наверняка знаете максимальные экстенты диапазона, даже если у вас недостаточно информации для дальнейшего сужения. Если вы знаете, что это небольшой список, но не знаете точного размера, сортировка может быть более простым решением.
JasonTrue
1
Или сначала выполните другой цикл по списку, чтобы найти самый маленький и самый большой элемент. Затем вы можете выделить массив точного размера с наименьшим значением в качестве базового смещения. Все еще O (N).
Безопасный
1
@JPatrick: Не домашняя работа, бизнес, я закончил CS лет назад :).
Фабиан Цейндл
4

Если сначала отсортировать весь список, то вы гарантируете время выполнения в худшем случае. Кроме того, выбор алгоритма сортировки имеет решающее значение.

Вот как я могу подойти к этой проблеме:

  1. Используйте сортировку кучи , сосредотачиваясь на самых маленьких элементах в списке.
  2. После каждого обмена проверяйте, есть ли у вас разрыв.
  3. Если вы найдете пробел, то return: Вы нашли свой ответ.
  4. Если вы не нашли разрыв, продолжайте обмениваться.

Вот визуализация кучи .

Джим Г.
источник
Один вопрос, как вы определяете «самые маленькие» элементы списка?
Джодрелл
4

Просто чтобы быть эзотерическим и «умным», в особом случае массива, имеющего только одну «дыру», вы можете попробовать решение на основе XOR:

  • Определите диапазон вашего массива; это делается путем установки переменных «max» и «min» для первого элемента массива, и для каждого последующего элемента, если этот элемент меньше чем min или больше чем max, установите min или max на новое значение.
  • Если диапазон на единицу меньше мощности множества, то есть только одна «дыра», поэтому вы можете использовать XOR.
  • Инициализируйте целочисленную переменную X до нуля.
  • Для каждого целого числа от минимального до максимального включительно, XOR это значение с X и сохранить результат в X.
  • Теперь XOR каждого целого числа в массиве с X, сохраняя каждый последующий результат в X, как и раньше.
  • Когда вы закончите, X будет значением вашей "дыры".

Это будет выполняться примерно в 2N раза по аналогии с решением bitvector, но для любого N> sizeof (int) требуется меньше места в памяти. Однако, если массив имеет несколько «отверстий», X будет «суммой» XOR всех отверстий, которые будет трудно или невозможно разделить на фактические значения отверстий. В этом случае вы прибегаете к другому методу, такому как подходы «pivot» или «bitvector» из других ответов.

Вы также можете повторить это, используя что-то похожее на метод pivot, чтобы еще больше снизить сложность. Переставьте массив на основе точки поворота (которая будет максимальным с левой стороны и минимальным с правой; это будет тривиально найти максимальный и минимальный значения полного массива при повороте). Если на левой стороне оси есть одно или несколько отверстий, вернитесь только на эту сторону; в противном случае вернитесь на другую сторону. В любой точке, где вы можете определить, что есть только одна дыра, используйте метод XOR, чтобы найти ее (которая должна быть дешевле в целом, чем продолжение поворота до набора из двух элементов с известной дырой, что является базовым случаем для чистый алгоритм поворота).

Keiths
источник
Это невероятно умно и круто! Теперь вы можете придумать способ сделать это с переменным количеством отверстий? :-D
2

Какой диапазон номеров вы встретите? Если этот диапазон не очень большой, вы можете решить это с помощью двух сканирований (линейное время O (n)), используя массив с таким количеством элементов, как у вас есть числа, торгуя пространством для времени. Вы можете найти диапазон динамически с помощью еще одного сканирования. Чтобы уменьшить пространство, вы можете назначить 1 бит каждому номеру, давая вам 8 номеров хранения на байт.

Другой вариант, который может быть лучше для ранних сценариев и был бы необходим вместо копирования памяти, состоит в том, чтобы изменить сортировку выбора так, чтобы она выходила раньше, если мин, найденный за проход сканирования, не на 1 больше, чем последний найденный мин.

Питер Смит
источник
1

Нет, не совсем. Поскольку любое еще не отсканированное число всегда может быть тем, которое заполняет данную «дыру», вы не можете избежать сканирования каждого числа хотя бы один раз, а затем сравнить его с его возможными соседями. Вы, вероятно, могли бы ускорить процесс, создав двоичное дерево или около того, а затем обойдя его слева направо, пока не будет найдена дыра, но это по сути та же сложность времени, что и сортировка, поскольку она сортирует. И вы, вероятно, не будете придумывать что-либо быстрее, чем Тимсорт .

pillmuncher
источник
1
Вы говорите, что обход списка такой же сложности, как и сортировка?
maple_shaft
@maple_shaft: Нет, я говорю, что построение двоичного дерева из случайных данных, а затем его обход слева направо эквивалентно сортировке, а затем переходу от малого к большому.
pillmuncher
1

Большинство идей здесь не более, чем просто сортировка. Версия bitvector является простой Bucketsort. Вид кучи также был упомянут. Это в основном сводится к выбору правильного алгоритма сортировки, который зависит от требований времени / пространства, а также от диапазона и количества элементов.

На мой взгляд, использование структуры кучи, вероятно, является наиболее общим решением (в основном, куча дает вам самые маленькие элементы эффективно без полной сортировки).

Вы также можете проанализировать подходы, которые сначала находят наименьшие числа, а затем сканируют каждое целое число больше этого. Или вы найдете 5 самых маленьких чисел, надеясь, что пробел будет.

Все эти алгоритмы имеют свою силу в зависимости от входных характеристик и требований программы.

Gerenuk
источник
0

Решение, которое не использует дополнительное хранилище или не принимает ширину (32 бита) целых чисел.

  1. За один линейный проход найдите наименьшее число. Давайте назовем это "мин". O (n) сложность времени.

  2. Выберите случайный элемент pivot и создайте раздел в стиле быстрой сортировки.

  3. Если ось оказалась в позиции = («pivot» - «min»), выполните рекурсивный переход с правой стороны раздела, иначе рекурсивный переход с левой стороны раздела. Идея заключается в том, что если бы с самого начала не было отверстий, шарнир находился бы в ("pivot" - "min") -й позиции, поэтому первое отверстие должно находиться справа от перегородки и наоборот.

  4. Базовый случай - это массив из 1 элемента, и дыра находится между этим элементом и следующим.

Ожидаемая общая сложность времени выполнения составляет O (n) (8 * n с константами), а наихудший случай равен O (n ^ 2). Анализ сложности времени для аналогичной проблемы можно найти здесь .

aufather
источник
0

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

Идея, лежащая в основе этого метода, похожа на быструю сортировку, в которой мы находим стержень и разделяем его, а затем возвращаемся на сторону (и) с отверстием. Чтобы увидеть, на каких сторонах есть отверстие, мы находим самые низкие и самые высокие числа и сравниваем их с осью и количеством значений на этой стороне. Скажем, точка разворота 17, а минимальное число - 11. Если отверстий нет, должно быть 6 чисел (11, 12, 13, 14, 15, 16, 17). Если есть 5, мы знаем, что на этой стороне есть дыра, и мы можем пройти только на той стороне, чтобы найти ее. У меня проблемы с объяснением этого более четко, поэтому давайте рассмотрим пример.

15 21 10 13 18 16 22 23 24 20 17 11 25 12 14

Pivot:

10 13 11 12 14 |15| 21 18 16 22 23 24 20 17 25

15 - это ось, обозначенная трубками ( ||). На левой стороне оси 5 цифр, как должно быть (15 - 10), и 9 справа, где должно быть 10 (25 - 15). Итак, мы возвращаемся с правой стороны; отметим, что предыдущая граница была 15 в случае, если дыра находится рядом с ней (16).

[15] 18 16 17 20 |21| 22 23 24 25

Теперь на левой стороне 4 цифры, но должно быть 5 (21 - 16). Итак, мы вернемся туда и снова отметим предыдущую границу (в скобках).

[15] 16 17 |18| 20 [21]

Левая сторона имеет правильные 2 числа (18 - 16), но правая имеет 1 вместо 2 (20 - 18). В зависимости от наших условий окончания, мы можем сравнить число 1 с двумя сторонами (18, 20) и увидеть, что 19 отсутствует, или повторить еще раз:

[18] |20| [21]

Левая сторона имеет нулевой размер с зазором между осью (20) и предыдущей границей (18), поэтому 19 - это отверстие.

*: Если есть дубликаты, вы, вероятно, могли бы использовать хэш-набор, чтобы удалить их за O (N), сохраняя общий метод O (N), но это может занять больше времени, чем при использовании какого-либо другого метода.

Kevin
источник
1
Я не верю, что OP сказал что-то о том, что там только одна дыра. Ввод представляет собой несортированный список чисел - они могут быть чем угодно. Из вашего описания непонятно, как бы вы определили, сколько цифр «должно быть».
Калеб
@caleb Не имеет значения, сколько существует дыр, просто нет дубликатов (которые можно удалить в O (N) с помощью хэш-набора, хотя на практике это может иметь больше служебных данных, чем другие методы). Я попытался улучшить описание, посмотреть, лучше ли.
Кевин
Это не линейно, ИМО. Это больше похоже на (logN) ^ 2. На каждом шаге вы поворачиваете подмножество интересующей вас коллекции (половину предыдущего подмассива, который вы определили как имеющий первую «дыру»), затем возвращаетесь в любую левую сторону, если в ней есть «дыра», или правая сторона, если левая сторона нет. (logN) ^ 2 все еще лучше, чем линейный; если N увеличивается в десять раз, вы делаете только порядка 2 (log (N) -1) + еще 1 шаг.
KeithS
@Keith - к сожалению, вам нужно посмотреть на все числа на каждом уровне, чтобы повернуть их, поэтому потребуется около n + n / 2 + n / 4 + ... = 2n (технически, 2 (нм)) сравнений ,
Кевин