Быстрый выбор с повторными значениями
Можно ли выполнить поиск k-го элемента в O(n) по мультимножеству (значения могут повторяться)?
Потому что, насколько я понимаю, идея быстрого выбора, я должен разделить ввод с помощью некоторого центра. Затем у меня есть 2 массива, которые я выбираю для рекурсивного поиска, зависит от того, какой элемент индекса я ищу + каков размер обоих массивов, например:
1 7 8 5 3 2 4
Допустим, pivot равен 4, я ищу второй по величине элемент. Так что после разбиения я мог бы получить порядок как
1 3 2 4 7 8 5
Поскольку правый подмассив состоит из 3 элементов, я все равно попытаюсь найти второе по величине в правом массиве, если я прав?
Но если бы я взял 8 как опору, я мог бы получить что-то вроде
1 3 2 7 5 4 8
и поэтому я постараюсь найти наибольший элемент в левой таблице (возможно, линейным, но в целом я возьму левый подмассив и поищу элемент - (| размер правого подмассива | + 1))
Но как насчет мультимножеств? Допустим, у меня есть массив:
4 5 6 7 7 7 4 3 2 1
и мой стержень 6 поиска 3-й самый большой элемент, после раздела я получаю:
4 5 3 2 4 1 6 7 7 7
так что, если я использую подход, представленный выше, я попытаюсь выполнить рекурсивный код на правом подмассиве, в то время как очевидно, что третье наибольшее значение равно 5, которое слева?
Единственное решение, которое я придумал, - это использовать некоторую структуру данных, такую как BST, Set и т. Д., Чтобы O(nlogn) отфильтровывал повторы. А затем используйте O (N) быстрого выбора. Однако в целом это дало бы мне нелинейный подход, это можно сделать линейным?
У меня также есть дополнительный вопрос, что, если выделение памяти не может быть сделано? И что я могу сделать, это использовать только локальные int + стека рекурсии. Проблема может быть решена в O (N)? Потому что O(nlogn) можно сделать, отсортировав + линейный "пройти счет".
1 ответ
Я думаю, что это зависит от вашей интерпретации "k-го по величине элемента". Если под "k-м наибольшим элементом" вы подразумеваете "элемент, который был бы в позиции k в массиве, если бы он был отсортирован", тогда quickselect будет работать без изменений.
Если, с другой стороны, вы имеете в виду "k-е наибольшее из различных значений в массиве", то вы правы, что немодифицированный быстрый выбор не будет работать правильно, как показывает ваш пример. Однако вы можете изменить алгоритм так, чтобы он работал в ожидаемое время O(n), добавив все элементы в хеш-таблицу, а затем итерируя по хеш-таблице, чтобы получить одну копию каждого отдельного значения. Оттуда вы можете использовать обычный алгоритм быстрого выбора для этого сгенерированного массива, который потребует всего O(n) времени ожидания.
Надеюсь это поможет!