Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find top N elements in an Array

What would be the best solution to find top N (say 10) elements in an unordered list (of say 100).

The solution which came in my head was to 1. sort it using quick sort, 2. get top 10.

But is there any better alternative?

like image 610
zengr Avatar asked Nov 03 '10 05:11

zengr


People also ask

How do you find the 3 Max elements in an array?

Solution Approachif (arr[i] > max) -> max3 = max2, max2 = max , max = arr[i]. else if (arr[i] > max2) -> max3 = max2, max2 = arr[i]. else if (arr[i] > max3) -> max3 = arr[i]. At the end of the loop, we will print all three values.

How do you find the top 2 numbers in an array?

Take two variables and initiliaze them with zero. Iterate through each element of the array and compare each number against these two number. If current number is greater than maxOne then maxOne = number and maxTwo = maxOne. Otherwise if it only greater than maxTwo then we only update maxTwo with current number.

How do you find the N largest element in an array?

To find the largest element, the first two elements of array are checked and the largest of these two elements are placed in arr[0] the first and third elements are checked and largest of these two elements is placed in arr[0] . this process continues until the first and last elements are checked.


1 Answers

The time could be reduced to linear time:

  1. Use the selection algorithm, which effectively find the k-th element in a un-sorted array in linear time. You can either use a variant of quick sort or more robust algorithms.

  2. Get the top k using the pivot got in step 1.

like image 89
Yin Zhu Avatar answered Sep 30 '22 13:09

Yin Zhu