Table of Contents
Given an array A of size N and a number K. The challenge is to find K-th largest number in the array, i.e., K-th order statistic.
The basic idea – to use the idea of quick sort algorithm. Actually, the algorithm is simple, it is more difficult to prove that it runs in an average of O(N), in contrast to the quick sort.
1. Implementation (not recursive):
template <class T> T order_statistics (std::vector<T> a, unsigned n, unsigned k) { using std::swap; for (unsigned l=1, r=n; ; ) { if (r <= l+1) { // the current part size is either 1 or 2, so it is easy to find the answer if (r == l+1 && a[r] < a[l]) swap (a[l], a[r]); return a[k]; } // ordering a[l], a[l+1], a[r] unsigned mid = (l + r) >> 1; swap (a[mid], a[l+1]); if (a[l] > a[r]) swap (a[l], a[r]); if (a[l+1] > a[r]) swap (a[l+1], a[r]); if (a[l] > a[l+1]) swap (a[l], a[l+1]); // performing division // barrier is a[l + 1], i.e. median among a[l], a[l + 1], a[r] unsigned i = l+1, j = r; const T cur = a[l+1]; for (;;) { while (a[++i] < cur) ; while (a[--j] > cur) ; if (i > j) break; swap (a[i], a[j]); } // inserting the barrier a[l+1] = a[j]; a[j] = cur; // we continue to work in that part, which must contain the required element if (j >= k) r = j-1; if (j <= k) l = i; } }
To note, in the standard C ++ library, this algorithm has already been implemented – it is called nth_element.
2. Practice Problems
Related posts:
Finding repetitions
Graph Reconstruction
Tanya and Password
Breaking Good
Xenia and Hamming
Learning and Improving Algorithm through contests - Antti Laaksonen
Dima and Horses
Exercising Walk
Dima and Game
Degenerate Matrix
Graph Coloring
Gold Experience
Maximum Distance
Segment Tree
Three strings
Playing with Permutations
Tape
Huffman Coding on Segment
Manacher's Algorithm - Finding all sub-palindromes in $O(N)$
Eugene and an array
Washer, Dryer, Folder
Bags and Coins
Students Initiation
Superhero's Job
Ordering T-Shirts
Bear and Poker
Buy Low Sell High
Finding common tangents to two circles
Color the Carpet
Clockwork Bomb
New Year and Ascent Sequence
Circle of Numbers