Поиск N-го элемента несортированного списка без сортировки списка

Ответ 1

Для сортировки потребуется минимальное время выполнения O (nlogn). Существуют очень эффективные алгоритмы выбора, которые могут решить вашу проблему в линейном времени.

Partition-based selection (иногда Quick select), основанный на идее быстрой сортировки (рекурсивное разбиение), является хорошим решением (см. ссылку для псевдокода + Другой пример).

Ответ 2

Куча - лучшая структура данных для этой операции, и у 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

Ответ 3

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

Ответ 4

Простая модифицированная быстродействующая сортировка очень хорошо работает на практике. Он имеет среднее время работы, пропорциональное N (хотя наихудшее время неудачи - O (N ^ 2)).

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

Ответ 5

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

Ответ 6

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

Ответ 7

Вы действительно хотите создать список "top-N" и выбрать тот, который находится в конце этого списка.

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

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

Пример для int и 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);
    }
}

Ответ 8

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

Однако вы можете сохранить самые большие значения Kth в качестве двоичного дерева, и операция станет 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)

Ответ 9

Одна вещь, которую вы должны сделать, если это в производственном коде, - это тест с образцами ваших данных. Например, вы можете рассмотреть массивы размером 1000 или 10000 элементов, а также создать метод быстрого выбора из рецепта.

Скомпилированный характер отсортированных и несколько скрытых и постоянно меняющихся оптимизаций делает его быстрее, чем написанный на питоне метод quickselect для наборов данных малого и среднего размера (< 1,000,000 элементов). Кроме того, вы можете найти, когда вы увеличиваете размер массива, превышающего эту величину, память более эффективно обрабатывается в собственном коде, и преимущество сохраняется.

Таким образом, даже если quickselect - это O (n) vs sorted O (nlogn), это не учитывает, сколько фактических инструкций машинного кода обрабатывает каждый n элементов, любые воздействия на конвейерную обработку, использование кэшей процессора и другие вещи, которые создатели и сторонники сортировки будут испепеляться в коде python.