Нахождение Энного объекта неотсортированного списка, не сортируя список

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

Простая модифицированная быстрая сортировка очень хорошо работает на практике. Его среднее время выполнения пропорционально N (хотя в худшем случае время выполнения невезения равно O (N ^ 2)).

Действуйте как быстрая сортировка. Случайным образом выберите значение поворота, затем просмотрите свои значения и посмотрите, находятся ли они выше или ниже этого значения поворота, и поместите их в две ячейки на основе этого сравнения. Затем в быстрой сортировке вы рекурсивно отсортируете каждую из этих двух корзин. Но для вычисления N-го наивысшего значения вам нужно отсортировать только ОДНУ из ячеек. Население каждой ячейки сообщает вам, в какой ячейке содержится n-е наивысшее значение. Так, например, если вам нужно 125-е по величине значение, и вы сортируете по двум ячейкам, у которых 75 в «высоком» контейнере и 150 в «нижнем», вы можете проигнорировать высокое значение и просто перейти к поиску 125-75 = 50-е по величине значение только в нижней ячейке.

Использовать heapsort. Он только частично упорядочивает список, пока вы не вытянете элементы.

По сути, вы хотите создать список «top-N» и выбрать тот, который находится в конце этого списка.

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

После завершения сканирования выберите последний элемент в списке первых N.

Пример для целых чисел и N = 5:

int[] top5 = new int[5]();
top5[0] = top5[1] = top5[2] = top5[3] = top5[4] = 0x80000000; // or your min value

for(int i = 0; i < largeArray.length; i++) {
    if(largeArray[i] > top5[4]) {
       // insert into top5:
       top5[4] = largeArray[i];

       // resort:
       quickSort(top5);
    }
}

Как уже говорилось, вы можете пройтись по списку, отслеживая K наибольших значений. Если K велико, этот алгоритм будет близок к O (n ² ).

Однако вы можете сохранить свои K-е самые большие значения в виде двоичного дерева, и операция станет O (n log k).

Согласно Википедии, это лучший алгоритм выбора:

 function findFirstK(list, left, right, k)
     if right > left
         select pivotIndex between left and right
         pivotNewIndex := partition(list, left, right, pivotIndex)
         if pivotNewIndex > k  // new condition
             findFirstK(list, left, pivotNewIndex-1, k)
         if pivotNewIndex < k
             findFirstK(list, pivotNewIndex+1, right, k)

Его сложность O (n)

Куча - лучшая структура данных для этой операции, и Python имеет отличную встроенную библиотеку для этого, называемую heapq.

import heapq

def nth_largest(n, iter):
    return heapq.nlargest(n, iter)[-1]

Пример использования:

>>> import random
>>> iter = [random.randint(0,1000) for i in range(100)]
>>> n = 10
>>> nth_largest(n, iter)
920

Подтвердите результат сортировкой :

>>> list(sorted(iter))[-10]
920

Используйте dev.new () . (См. этот связанный вопрос .)

plot(1:10)
dev.new(width=5, height=4)
plot(1:20)

Чтобы быть более конкретным, какие единицы используются:

dev.new(width=5, height=4, unit="in")
plot(1:20)
dev.new(width = 550, height = 330, unit = "px")
plot(1:15)

Вы должны включить следующее в single.php вашего шаблона, чтобы включить комментарии:

<?php comments_template(); ?>

Используйте шаблон по умолчанию, который поставляется с WordPress в качестве ссылки.

Даг Нейнер добавил это в качестве комментария первым, поэтому, если он разместит это в качестве ответа, пожалуйста, выберите его.

Вы можете попробовать метод Median of Medians - это скорость O (N).