Find the k largest elements in order

Question

What is the fastest way to find the k largest elements in an array in order (i.e., starting from the largest element to the kth largest element)?

Answer 1

One of the options:

• Using a linear selection algorithm, like medians of medians or introsort, find the kth largest element and rearrange the elements so that all elements from the kth element are ahead larger than the kth element.

• Sort all items from kth ahead using a fast sorting algorithm like heapsort or quicksort.

Step (1) takes time O (n), and step (2) takes time O (k log k). In general, the algorithm runs in O (n + k log k) time, which is very, very fast.

Hope this helps!

Answer 2

C ++ also provides a partial_sort algorithm that solves the problem of selecting the smallest k elements (sorted) with O (n log k) time complexity. The algorithm is not intended to select the largest k elements, since this should be done by inverting the ordering predicate.

For Perl, the Sort :: Key :: Top module, available from CPAN, provides a set of functions for selecting the top n elements from a list using several ordering procedures and custom key extraction procedures. In addition, the Statistics :: CaseResampling module provides a function for calculating quantiles using quickselect.

The Python standard library (starting with version 2.4) includes heapq.nsmallest () and nlargest (), which return sorted lists, the first in O (n + k log n), the last in O (n log k) time.

Answer 3

Radix Sort Solution:

• Sort an array in descending order using radix sort;
• Print the first elements of K.

Time complexity: O (N * L), where L = the length of the largest element, can take L = O (1). Used space: O (N) for sorting by base.

However, I think that the radix socket has a lot of overhead, which makes its linear time complexity less attractive.

Answer 4

1) Create a Max Heap tree in O (n)
2) Use Extract Max k times to get k maximum elements from Max Heap O (klogn)

Difficulty of time: O (n + klogn)

An implementation of C ++ using STL is given below:

#include <iostream> #include<bits/stdc++.h> using namespace std; int main() { int arr[] = {4,3,7,12,23,1,8,5,9,2}; //Lets extract 3 maximum elements int k = 3; //First convert the array to a vector to use STL vector<int> vec; for(int i=0;i<10;i++){ vec.push_back(arr[i]); } //Build heap in O(n) make_heap(vec.begin(), vec.end()); //Extract max k times for(int i=0;i<k;i++){ cout<<vec.front()<<" "; pop_heap(vec.begin(),vec.end()); vec.pop_back(); } return 0; } 

Answer 5

The @templatetypedef solution is probably the fastest, assuming you can modify or copy input.

Alternatively, you can use heap or BST ( set in C ++) to store the k largest elements at the moment, and then read the elements of the array one by one. Although this is O (n lg k), it does not change the input and uses only O (k) additional memory. It also works with streams (when you do not know all the data from the very beginning).

Answer 6

Here is a solution with O(N + k lg k) complexity.

 int[] kLargest_Dremio(int[] A, int k) { int[] result = new int[k]; shouldGetIndex = true; int q = AreIndicesValid(0, A.Length - 1) ? RandomizedSelet(0, A.Length-1, A.Length-k+1) : -1; Array.Copy(A, q, result, 0, k); Array.Sort(result, (a, b) => { return a>b; }); return result; } 

AreIndicesValid and RandomizedSelet defined in this github source file .

Answer 7

The question arose about performance and limited resources.

Create a value class for the first three values. Use such a battery to reduce in parallel flow. Limit concurrency according to context (memory, power).

 class BronzeSilverGold { int[] values = new int[] {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE}; // For reduction void add(int x) { ... } // For combining two results of two threads. void merge(BronzeSilverGold other) { ... } } 

Concurrency should be limited in your constellation, so specify N_THREADS in:

 try { ForkJoinPool threadPool = new ForkJoinPool(N_THREADS); threadPool.submit(() -> { BronzeSilverGold result = IntStream.of(...).parallel().collect( BronzeSilverGold::new, (bsg, n) -> BronzeSilverGold::add, (bsg1, bsg2) -> bsg1.merge(bsg2)); ... }); } catch (InterruptedException | ExecutionException e) { prrtl(); }