Существует неупорядоченный массив из n целых чисел.Я хочу найти кратчайшее расстояние между двумя элементами в O (n).
n
Спасибо!
ПРИМЕЧАНИЕ: радикальная сортировка не подходит из-за сложности времени.
В модели вычисления алгебраического дерева решений это проблема Ω (n log n).Ограничение на неограниченные целые числа не очень помогает.