Problem
Find nth largest element in an array of m elements where n->0 (n is much smaller than m) without sorting
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find nth largest element in an array of m elements where n->0 (n is much smaller than m) without sorting
Created Data : 28-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <limits>
using namespace std;
void InsertCandidate(int* arr, int len, int num)
{
int i, j;
for(i = len - 1; i >=0; --i){
if(num > arr[i]) break;
}
for(j = 1; j <= i; ++j){
arr[j-1] = arr[j];
}
arr[i] = num;
}
int FindNthLargestNum(int* arr, int len, int nth)
{
int* candidates = new int[nth];
for(int i = 0; i < nth; ++i){
candidates[i] = numeric_limits<int>::min();
}
for(int i = 0; i < len; ++i){
if(arr[i] > candidates[0]){
InsertCandidate(candidates, nth, arr[i]);
}
}
int retVal = candidates[0];
delete[] candidates;
return retVal;
}
int main(int argc, char* argv[])
{
int arr[20] = {0};
for(int i = 10; i < 20; ++i){
cout << "The array is " << endl;
for(int j = 0; j < sizeof(arr)/sizeof(arr[0]); ++j){
arr[j] = rand() % 100;
cout << setw(5) << arr[j];
}
cout << endl;
for(int j = 1; j < 5 ; ++j){
cout << "The " << j << "th maximum is" ;
cout << FindNthLargestNum(arr, sizeof(arr)/sizeof(arr[0]), j) << endl;
}
cout << "----------------------------" << endl;
}
return 0;
}
Output
The array is
41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36
The 1th maximum is95
The 2th maximum is91
The 3th maximum is81
The 4th maximum is78
----------------------------
The array is
91 4 2 53 92 82 21 16 18 95 47 26 71 38 69 12 67 99 35 94
The 1th maximum is99
The 2th maximum is95
The 3th maximum is94
The 4th maximum is92
----------------------------
The array is
3 11 22 33 73 64 41 11 53 68 47 44 62 57 37 59 23 41 29 78
The 1th maximum is78
The 2th maximum is73
The 3th maximum is68
The 4th maximum is64
----------------------------
The array is
16 35 90 42 88 6 40 42 64 48 46 5 90 29 70 50 6 1 93 48
The 1th maximum is93
The 2th maximum is90
The 3th maximum is90
The 4th maximum is88
----------------------------
The array is
29 23 84 54 56 40 66 76 31 8 44 39 26 23 37 38 18 82 29 41
The 1th maximum is84
The 2th maximum is82
The 3th maximum is76
The 4th maximum is66
----------------------------
The array is
33 15 39 58 4 30 77 6 73 86 21 45 24 72 70 29 77 73 97 12
The 1th maximum is97
The 2th maximum is86
The 3th maximum is77
The 4th maximum is77
----------------------------
The array is
86 90 61 36 55 67 55 74 31 52 50 50 41 24 66 30 7 91 7 37
The 1th maximum is91
The 2th maximum is90
The 3th maximum is86
The 4th maximum is74
----------------------------
The array is
57 87 53 83 45 9 9 58 21 88 22 46 6 30 13 68 0 91 62 55
The 1th maximum is91
The 2th maximum is88
The 3th maximum is87
The 4th maximum is83
----------------------------
The array is
10 59 24 37 48 83 95 41 2 50 91 36 74 20 96 21 48 99 68 84
The 1th maximum is99
The 2th maximum is96
The 3th maximum is95
The 4th maximum is91
----------------------------
The array is
81 34 53 99 18 38 0 88 27 67 28 93 48 83 7 21 10 17 13 14
The 1th maximum is99
The 2th maximum is93
The 3th maximum is88
The 4th maximum is83
----------------------------
Press any key to continue . . .