HekpoMaH's blog

Any Idea
By HekpoMaH, 12 years ago, In English

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

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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").

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

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

    even simpler , change k to n-k+1

    → Reply
»
12 years ago, # |
  Vote: I like it -7 Vote: I do not like it

O(n) algorithm is also described here

→ Reply
»
12 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Your nickname reminds me something...

→ Reply