Вот эта вещь. Я делал leetcode 164 Maximum Gap. Оптимальным решением для этого является сортировка ведром.
Это заставляет меня задуматься о проблеме сортировки. Допустим, у нас есть следующий список:
2, 5, 19, 444, -14, 89, 16, 77
для того, что я думаю, мы можем расположить эти числа двумя различнымидиапазон, (мин, середина) (середина, максимум) и середина должны быть мин + (макс - мин) / 2;
Таким образом, мы получили (-14, 215) (216, 444)
, мы установили min в крайнее левое положение и max в крайнее правое положение и заполнили другой элемент на основе диапазона, тогда мы получили
-14 2, 5, 19, 89, 16, 77
444
мы напоминаем сортировку для двух диапазонов, а для левого мы имеем (-14, 37) (38, 89) и список
-14 2, 5, 19, 16
77 89
рекурсия, тогда у нас будет отсортированный список;
Я устал писать это, оно работает. Время выполнения - O (n log (n)), а сложность пространства - O (n) Если честно, я все еще студент и не очень хорош в алгоритме. Так что я действительно не могу сделать это лучше. Я просто хочу спросить, возможно ли, что этот может быть намного быстрее, чем n logn. Я имею в виду худший случай, а не особую ситуацию.