Как найти kth самый большой элемент в неотсортированном массиве длины n в O (n)?

То, что я сделал бы, является этим:

initialize empty doubly linked list l
for each element e in array
    if e larger than head(l)
        make e the new head of l
        if size(l) > k
            remove last element from l

the last element of l should now be the kth largest element

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

Обновление:

initialize empty sorted tree l
for each element e in array
    if e between head(l) and tail(l)
        insert e into l // O(log k)
        if size(l) > k
            remove last element from l

the last element of l should now be the kth largest element

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

Можно сделать это в O (n + kn) = O (n) (для постоянного k) в течение времени и O (k) для пространства путем отслеживания k самые большие элементы, которые Вы видели.

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

приоритетное решение для "кучи" Warren's более опрятно все же.

Компаньон Программиста А к Анализу Алгоритма дает версию, которая является O (n), хотя автор заявляет, что постоянный множитель так высок, Вы, вероятно, предпочли бы наивный sort-the-list-then-select метод.

я ответил на букву Вашего вопроса:)

Библиотека стандарта C++ имеет почти точно, что функция вызов nth_element, хотя это действительно изменяет Ваши данные. Это ожидало линейное время выполнения, O (N), и это также делает частичный вид.

const int N = ...;
double a[N];
// ... 
const int m = ...; // m < N
nth_element (a, a + m, a + N);
// a[m] contains the mth element in a

Быстрый Google на том ('kth самый большой массив элемента') возвратил это: http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17

"Make one pass through tracking the three largest values so far." 

(это было специально для 3-го по величине)

и этот ответ:

Build a heap/priority queue.  O(n)
Pop top element.  O(log n)
Pop top element.  O(log n)
Pop top element.  O(log n)

Total = O(n) + 3 O(log n) = O(n)

Если Вы хотите истинное O(n) алгоритм, в противоположность O(kn) или что-то как этот, то необходимо использовать quickselect (это в основном quicksort, где Вы выводите раздел, что Вы не интересуетесь). У моего профессора есть большая рецензия с анализом во время выполнения: ( ссылка )

алгоритм QuickSelect быстро находит k-th самый маленький элемент неотсортированного массива n элементы. Это RandomizedAlgorithm, таким образом, мы вычисляем худший случай , ожидал время выполнения.

Вот алгоритм.

QuickSelect(A, k)
  let r be chosen uniformly at random in the range 1 to length(A)
  let pivot = A[r]
  let A1, A2 be new arrays
  # split into a pile A1 of small elements and A2 of big elements
  for i = 1 to n
    if A[i] < pivot then
      append A[i] to A1
    else if A[i] > pivot then
      append A[i] to A2
    else
      # do nothing
  end for
  if k <= length(A1):
    # it's in the pile of small elements
    return QuickSelect(A1, k)
  else if k > length(A) - length(A2)
    # it's in the pile of big elements
    return QuickSelect(A2, k - (length(A) - length(A2))
  else
    # it's equal to the pivot
    return pivot

, Каково время выполнения этого алгоритма? Если противник зеркально отражает монеты для нас, мы можем найти, что центр всегда является самым большим элементом, и k всегда 1, давая время выполнения [1 130]

T(n) = Theta(n) + T(n-1) = Theta(n2)

, Но если выбор действительно случаен, ожидаемое время выполнения дано [1 131]

T(n) <= Theta(n) + (1/n) ∑i=1 to nT(max(i, n-i-1))

, где мы делаем не совсем разумное предположение, что рекурсия всегда приземляется в больших из [1 110] или A2.

Позволяют нам предположить это T(n) <= an для [приблизительно 1 113]. Тогда мы добираемся

T(n) 
 <= cn + (1/n) ∑i=1 to nT(max(i-1, n-i))
 = cn + (1/n) ∑i=1 to floor(n/2) T(n-i) + (1/n) ∑i=floor(n/2)+1 to n T(i)
 <= cn + 2 (1/n) ∑i=floor(n/2) to n T(i)
 <= cn + 2 (1/n) ∑i=floor(n/2) to n ai

, и теперь так или иначе мы должны заставить ужасающую сумму справа от знака "плюс" поглощать cn слева. Если мы просто связали его как [1 115], мы добираемся [примерно 1 116]. Но это является слишком большим - нет никакой комнаты для сжатия в дополнительном cn. Поэтому давайте развернем сумму с помощью арифметической серийной формулы:

∑i=floor(n/2) to n i  
 = ∑i=1 to n i - ∑i=1 to floor(n/2) i  
 = n(n+1)/2 - floor(n/2)(floor(n/2)+1)/2  
 <= n2/2 - (n/4)2/2  
 = (15/32)n2

, где мы используем в своих интересах n быть "достаточно большим" для замены ужасного floor(n/2) факторы с намного более чистый (и меньший) n/4. Теперь мы можем продолжить

cn + 2 (1/n) ∑i=floor(n/2) to n ai,
 <= cn + (2a/n) (15/32) n2
 = n (c + (15/16)a)
 <= an

, обеспечил a > 16c.

Это дает T(n) = O(n). Это ясно Omega(n), таким образом, мы добираемся T(n) = Theta(n).

Отрицательный просмотр назад не поддерживается до Ruby 1.9, но вы можете сделать нечто подобное, используя сканирование:

"xy y ay xy +y".scan(/([^x])(y)/) # => [[" ", "y"], ["a", "y"], ["+", "y"]]
"xy y ay xy +y".scan(/([^x])(y)/).map {|match| match[1]}  # => ["y", "y", "y"]

Конечно, это намного сложнее, если вы хотите избежать многого. перед y больше одного символа. Тогда вам нужно будет сделать что-то вроде:

Найдите медиану массива за линейное время, затем используйте процедуру разделения точно так же, как при быстрой сортировке, чтобы разделить массив на две части, значения слева от медиана меньше (<), чем медиана, и вправо больше, чем (>) медиана, это тоже можно сделать в строке во время, теперь перейдите к той части массива, где находится k-й элемент, Теперь повторение становится : T (n) = T (n / 2) + cn , что дает мне O (n) в целом.

Вам нравится быстрая сортировка. Выберите элемент наугад и засуньйте все либо выше, либо ниже. На этом этапе вы будете знать, какой элемент вы на самом деле выбрали, и если это kth-элемент, который вы закончили, в противном случае вы повторите с bin (выше или ниже), в который попадет kth-элемент. Статистически говоря, время, необходимое для поиска элемента kth, растет с n, O(n).