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:
King's Path
Antipalindrome
Kirchhoff's theorem. Finding the number of spanning trees
Morning run
Eugene and an array
The Child and Binary Tree
Travel Card
The Great Julya Calendar
Fence Planks
Fountains
Playing on Graph
Kay and Snowflake
Hate "A"
Modular Multiplicative Inverse
Lowest Common Ancestor - Farach-Colton and Bender Algorithm
Aroma's Search
Felicity is Coming!
Fox and Perfect Sets
Snake
Pavel and Triangles
Finding articulation points in a graph in $O(N+M)$
Equalize
Cow and Vacation
PolandBall and Gifts
Wise Men (Easy Version)
Ice Cream
Happy Line
Washer, Dryer, Folder
Rectangle Painting 2
Maximum flow - Push-relabel algorithm
Hydra
Graph Decomposition