Как мы можем найти самый большой элемент массива?

Question

Алгоритм поиска n-го наименьшего / наибольшего элемента в массиве с использованием структуры данных самобалансирующегося двоичного дерева поиска

Прочтите сообщение: Найдите k-й наименьший элемент в бинарном дереве поиска оптимальным способом . Но правильный ответ не ясен, так как я не могу найти правильный ответ, для примера, который я взял ...... Пожалуйста, требуется больше объяснений .......

Answer 1

C.A.R. Алгоритм Хоара select разработан именно для этой цели. Выполняется за [ожидаемое] линейное время с дополнительной логарифмической памятью.

Редактировать: очевидная альтернатива сортировки, а затем выбора правильного элемента имеет сложность O (N log N) вместо O (N). Хранение i самых больших элементов в отсортированном порядке требует O (i) вспомогательной памяти и примерно O (N * i log i) сложности. Это может быть выигрышем, если известно, что i a priori довольно мало (например, 1 или 2). Для более общего использования select обычно лучше.

Edit2: случайно, у меня нет хорошей ссылки, но я описал эту идею в предыдущем ответе .

Answer 2

Сначала отсортируйте массив по убыванию, затем возьмите i th элемент.

Answer 3

Создайте кучу из элементов и вызовите MIN i раз.

Answer 4

Create an empty list L

For each element x in the original list,

    add x in sorted position to L
    if L has more than i elements, 
        pop the smallest one off L

if List2 has i elements, 
    return the i-th element, 
else 
    return failure

Это должно занять O (N (log (i))).Если i считается константой, то это O (N).

Answer 5

Есть много стратегий, доступных для вашей задачи (если вы не сосредотачиваетесь на самобалансирующемся дереве с самого начала).

Обычно это компромиссная скорость / память.Большинство алгоритмов требуют либо изменения массива на месте, либо O(N) дополнительного хранилища.

Решение с самобалансирующимся деревом относится к последней категории, но здесь это неправильный выбор.Проблема в том, что построение самого дерева занимает O(N*log N), что будет доминировать в последующем поисковом запросе и даст окончательную сложность O(N*log N).Поэтому вы не лучше, чем просто сортировать массив и использовать сложную структуру данных ...

В общем, проблема во многом зависит от величины i, связанной с N.Если подумать минуту, для i == 1 это тривиально, верно?Это называется нахождением максимума.

Ну, та же самая стратегия, очевидно, работает для i == 2 (перенос двух элементов вокруг) в линейном времени.И это также тривиально симметрично: т. Е. Если вам нужно найти N-1-й элемент, просто возьмите с собой 2 минимальных элемента.

Однако он теряет эффективность, когда i равен N / 2 или N/ 4.Перенос элементов i Maximum означает сортировку массива размером i ... и, таким образом, мы отступаем к стене N*log N.

Джерри Коффин указал на простое решение, которое хорошо подходит для этого случая.Вот ссылка на Википедия .В полной статье также описывается метод «Медиана медианы»: он более надежен, но требует больше работы и, как правило, медленнее.

Answer 6

Это подходящая задача для куч, которые имеют очень низкую вставку и низкую стоимость delete_min. Например. сопряжение кучи . Это будет иметь худшую производительность O (n * log (n)). Но так как нетривиально реализовать, лучше проверить сначала предложенные в другом месте алгоритмы выбора .

Answer 7

Создайте отсортированную структуру данных для хранения элементов i и установите начальный счет в 0.

Обрабатывать каждый элемент в исходном массиве, добавляя его в эту новую структуру, пока новая структура не будет заполнена.

Затем обработайте оставшуюся часть исходного массива. Для каждого, который больше самого маленького в отсортированной структуре данных, удалите самое маленькое из этой структуры и вставьте новый.

Как только вы обработаете все элементы в исходном массиве, ваша структура будет содержать i наибольших элементов. Просто возьмите последний из них, и вы получите свой i 'величайший элемент.

Voila!

В качестве альтернативы, отсортируйте его, затем просто возьмите i '-ый элемент напрямую.