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:
Metro
Remove Duplicates
PolandBall and White-Red graph
Keyboard
Treap (Cartesian tree)
Rotate Columns (easy version)
Bots
Flowers and Chocolate
Prüfer code
Mind Control
Attack on Red Kingdom
Magnum Opus
Berland Elections
Design Tutorial: Inverse the Problem
Birthday
Travelling Through the Snow Queen's Kingdom
Arbitrary-Precision Arithmetic
Information Graph
Edge Weight Assignment
Ancient Prophesy
Fox and Box Accumulation
Equalize
The Maths Lecture
Cowslip Collections
Substitutes in Number
M-numbers
Ilya and a Colorful Walk
Practice
Increase Sequence
Yash And Trees
AND Segments
Fibonotci