September 1, 2010
kth Largest Element in an Array
Problem
Given an array of positive integers. Find the n(th) largest element in the array.
Solution
Sort the array in decreasing order then loop through the sorted array while counting unique elements then stop when the count is equal to (n). In the code below we will assume the array is already sorted. You can refer to the following post for more information about merge sort which you can use to efficiently sort the array in O(nlogn) time complexity
Code
Here is the C++ code to do that assuming the array is already sorted in decreasing order
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
//Includes #include <iostream> //STD using namespace std; //Main function void main() { //Input array (already sorted) int A[] = {6, 6, 5, 5, 5, 4, 3, 3, 2, 1}; //Array size int s = 10; //Let us assume we need to find the 3d //maximum which is 4 int n = 3; //Counter int c = 1; //Initialize n(th) max int nmax = A[0]; //Loop in the array while the count is less than (n) for (int i = 0; i < s && c < n; i++) { //If the current array element is different //from the current n(th) max increment the //counter if (A[i] != nmax) c++; //Update n(th) max nmax = A[i]; } //Once the loop above is finished //then n(th) max will be already calculated cout << nmax << endl; } |
About Author
Mohammed Abualrob
Software Engineer @ Cisco