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:
Maximum flow - MPM algorithm
Adam and Tree
Xor-Set
Au Pont Rouge
Robot Rapping Results Report
New Year and the Christmas Ornament
Modular Multiplicative Inverse
Vertical decomposition
Connected Components
The Great Julya Calendar
Convex Hull construction using Graham's Scan
Exploration plan
Calculating the determinant of a matrix by Gauss
Travelling Through the Snow Queen's Kingdom
Generate a String
Orchestra
Ehab's REAL Number Theory Problem
Crazy Diamond
Gennady and a Card Game
Rock Is Push
Bear and Blocks
String Set Queries
Josephus Problem
Chaotic V.
Hot is Cold
Good Subsets
King Moves
New Year and Permutation
Load Testing
Game with Powers
Golden System
Ancient Prophesy