Можно ли найти два числа, разница которых минимальна в O (n) времени

Ответ 1

Найти наименьший и самый большой элемент в списке. Наименьшая по величине разница будет минимальной.

Если вы ищете неотрицательную разницу, то это, конечно, по крайней мере так же сложно, как проверка того, имеет ли массив два одинаковых элемента. Это называется проблема уникальности элемента и без каких-либо дополнительных предположений (например, ограничение размера целых чисел, допускающих другие операции, кроме сравнения) требует >= n log n time, Это 1-мерный случай нахождения ближайшей пары точек .

Ответ 2

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

Ответ 3

Я думаю, что это возможно. Секрет в том, что вам действительно не нужно сортировать список, вам просто нужно создать подсчет чисел, которые существуют. Это может считаться "допущением" с алгоритмической точки зрения, но не с практической точки зрения. Мы знаем, что ints ограничены min и max.

Итак, создайте массив из 2-х битовых элементов, по одной паре для каждого int от INT_MIN до INT_MAX включительно, установите все из них на 00.

Итерации по всему списку чисел. Для каждого числа в списке, если соответствующие 2 бита равны 00, установите их на 01. Если они 01, установите их в 10. В противном случае игнорируйте. Это, очевидно, O (n).

Далее, если для любого из двух битов установлено значение 10, это ваш ответ. Минимальное расстояние равно 0, потому что список содержит повторяющееся число. Если нет, просмотрите список и найдите минимальное расстояние. Многие люди уже указали, что для этого существуют простые алгоритмы O (n).

So O (n) + O (n) = O (n).

Изменить: отвечать на комментарии.

Интересные моменты. Я думаю, что вы могли бы достичь тех же результатов, не делая никаких предположений, сначала найдя мин/макс списка и используя разреженный массив от min до max для хранения данных. Принимает во внимание предположение INT_MIN/MAX, сложность пространства и сложность времени O (m) сканирования массива.

Ответ 4

Самое лучшее, о чем я могу думать, это подсчет сортировки массива (возможно, объединение равных значений), а затем выполните отсортированные сравнения - bin sort - это O (n + M) (M - количество различных значений). Однако это требует большой памяти. Некоторая форма сортировки ковша или радикса будет промежуточной по времени и более эффективной в пространстве.

Ответ 5

Отсортировать список с radixsort (что является O (n) для целых чисел), затем перебирать и отслеживать наименьшее расстояние до сих пор.

(я предполагаю, что ваше целое число является типом фиксированного бита. Если они могут содержать произвольно большие математические целые числа, radixsort будет также O (n log n).)

Ответ 6

Это кажется возможным сортировать неограниченный набор целых чисел в O (n * sqrt (log (log (n))) time После сортировки, конечно, тривиально найти минимальную разницу в линейном времени.

Но я не могу придумать какой-либо алгоритм, чтобы сделать его быстрее, чем это.

Ответ 7

Нет, не делая предположений о числах/порядке.

Было бы возможно, учитывая отсортированный список.

Ответ 8

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

ИЗМЕНИТЬ. Хорошо, если вы действительно хотите спорить, тогда вопрос не говорит, должна ли она быть машиной Тьюринга или нет. С квантовыми компьютерами вы можете делать это в линейном времени:)