алгоритм за O (n) временной сложности, чтобы найти пару nos в массиве, которые имеют самую близкую разницу между собой

Question

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

Answer 1

Я почти уверен, что вы не можете получить общий линейный алгоритм времени для этой задачи!

Однако, поскольку у вас есть (ограниченные) целые числа, вы можете немного обмануть и начать сортировку массива с помощью radix sort, который является линейным временем!Затем просто найдите ближайшую соседнюю пару, которая снова линейна.

Answer 2

если вы ищете наименьшую абсолютную разницу между любой парой различных целых чисел, то алгоритм ltjax даст вам ответ в линейном времени.однако, поскольку проблема установлена, отрицательные числа действительны;в этом случае найдите самые большие, L и самые маленькие, S, числа, используя линейный поиск, тогда ответ S - L.

Answer 3

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

Answer 4

Я думаю, вы можете найти минимум два числа и найти разницу таким образом.Индекс i указывает на 0, индекс j указывает на 1, попробуйте найти min1 в четных индексах через i, найдите min2 в нечетных индексах через j в одной итерации и sub min1, min2.

Answer 5

Я думаю, что это может быть неправильно, если я получу первый минимальный элемент с помощью линейного поиска, а затем снова применю цикл для получения второго минимального элемента.например, min1 = A [0];для (i = 0; iA [i]) min1 = A [i];} min2 = A [1];для (i = 1; iA [i]) min2 = A [i];} diff = min2-min1;