Вернуть верхние элементы K из входного массива
Я ищу эффективный способ вернуться наверх k элементы из входного массива.
Одним из способов будет сортировка массива и возврат k элементы из конца массива.
Здесь предлагаются другие методы, один из которых использует алгоритм быстрого выбора, но, насколько я понимаю, быстрый выбор возвращает только k -ый элемент в несортированном массиве. После того, как он возвращается, элементы слева и справа от k все еще не отсортированы.
Так и должно быть примерно так:
while k>0{
quickselect(int[] arr, k);
k--;
}
Быстрый выбор O(n) и мы делаем это для k раз, поэтому общая сложность времени O(n*k),
Но данные в посте предполагают, что это лучше, чем O(n log n),
Выбор 200 лучших из миллиона образцов будет означать 200 million в первом случае, но 20 million в последнем. Очевидно, это намного лучше.
Мое понимание того, как можно использовать быстрый выбор для выбора правильных 200 элементов?
2 ответа
Нет не нужно O(nk) время - это можно сделать за O(n) (средний случай).
Конечным результатом быстрого выбора будет k-й элемент в k-й позиции от конца массива с меньшими элементами слева и большими элементами справа.
Таким образом, все элементы от этого элемента справа будут k самыми большими элементами - было бы тривиально извлечь их в O(k) (с простым циклом for), что в итоге дало бы общее время выполнения O(n),
В качестве альтернативы, поскольку вы знаете k-й элемент после выполнения быстрой выборки, вы можете просто снова пройти через массив и извлечь все элементы, большие или равные этому элементу (это можно сделать за один проход - также O(n)).
Вам понадобится дополнительный O(k log k) (сортировать их), если вы хотите вернуть их в отсортированном порядке.
Быстрый выбор удобен, если n не слишком велико, но если у вас очень большое n (слишком большое, чтобы уместиться в памяти) или неизвестное n (скажем, вы видите неограниченный поток выборок и хотите, чтобы вы могли сообщить о 200 самых больших из увиденных, поэтому далеко в любой точке), тогда альтернативой является сохранение минимальной кучи k-элемента, и каждый раз, когда вы видите новый элемент, сравнивайте его с вершиной минимальной кучи (наименьший из 200 самых больших элементов на данный момент), и если это больше, вытолкните старую вершину кучи и вставьте новый элемент в кучу.