Блог пользователя HekpoMaH

Any Idea
Автор HekpoMaH, 11 лет назад, По-английски

I am wondering about how to find the k-th biggest number in an array with less complexity than O(nlogn). Any ideas?

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

There is an O(n) algorithm for finding the kth order statistic (the kth smallest element) in the array. For finding the kth biggest element you can change comparator or just inverse signs of all numbers in the array. Algorithm that works O(n) in the worst case is described in Wikipedia: http://en.wikipedia.org/wiki/Selection_algorithm ("Linear general selection algorithm").

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    you can change comparator or just inverse signs of all numbers in the array

    even simpler , change k to n-k+1

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

O(n) algorithm is also described here

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Your nickname reminds me something...

→ Ответить