I am wondering about how to find the k-th biggest number in an array with less complexity than O(nlogn). Any ideas?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
I am wondering about how to find the k-th biggest number in an array with less complexity than O(nlogn). Any ideas?
Name |
---|
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").
you can change comparator or just inverse signs of all numbers in the array
even simpler , change k to n-k+1
O(n) algorithm is also described here
Your nickname reminds me something...