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:
Solving assignment problem using min-cost-flow
Kate and imperfection
Design Tutorial: Make It Nondeterministic
Divide and Conquer DP
Beautiful Sequence
Festival Organization
Hidden Bipartite Graph
Dreamoon Likes Coloring
Travelling Through the Snow Queen's Kingdom
Happy Cactus
Linear Diophantine Equation
Pumping Stations
Fox and Card Game
Encoding
Neural Network country
Falling Blocks
Limak and Shooting Points
Marvolo Gaunt's Ring
Primality tests
Basic Geometry
Teams
Bears and Juice
T-shirt buying
Cow and Treats
Robot Rapping Results Report
Wilbur and Swimming Pool
Antipalindrome
Fibonacci-ish II
Substring Search
Level Statistics
Fox and Box Accumulation
Length of the union of segments