Post date: Jul 28, 2013 2:29:6 AM
Problem
there are three shorted int Array
A1 : {2,4,9,16,19,68,78}
A2:{4,8,67,106,109,115,120}
A3:{9,15,19,108,119,130,190}
write an efficient algo to get the top 5 largest number from these three arrays.
Function would be like
int[] top5LargestNumber(int[] A1,int[] A2,int[] A3)
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find top 5 largest numbers for 3 sorted arrays
Created Data : 28-07-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <limits>
#include <iterator>
#include <cassert>
using namespace std;
inline int max3(int a, int b, int c)
{
return max(a, max(b, c));
}
void top5LargestNumber(int* a1, int len1, int* a2, int len2, int* a3, int len3, int* result, int& len)
{
len = min(len1 + len2 + len3, 5);
int i = len1 - 1;
int j = len2 - 1;
int k = len3 - 1;
int l(0);
while( l < len){
int e1 = a1[i];
int e2 = a2[j];
int e3 = a3[k];
if(i < 0) e1 = numeric_limits<int>::min();
if(j < 0) e2 = numeric_limits<int>::min();
if(k < 0) e3 = numeric_limits<int>::min();
int value = max3(e1, e2, e3);
if(value == e1) i --;
else if(value == e2) j --;
else k --;
result[l++] = value;
}
}
void DoTest(int* a1, int len1, int* a2, int len2, int* a3, int len3)
{
assert(a1 != NULL && len1 > 0);
assert(a2 != NULL && len2 > 0);
assert(a3 != NULL && len3 > 0);
cout << "Array 1 -- ";
copy(a1, a1 + len1, ostream_iterator<int>(cout, " "));
cout << endl;
cout << "Array 2 -- ";
copy(a2, a2 + len2, ostream_iterator<int>(cout, " "));
cout << endl;
cout << "Array 3 -- ";
copy(a3, a3 + len3, ostream_iterator<int>(cout, " "));
cout << endl;
int result[5];
int len;
top5LargestNumber(a1, len1, a2, len2, a3, len3, result, len);
cout << "The top five -- ";
copy(result, result + len, ostream_iterator<int>(cout, " "));
cout << endl;
cout << "-----------------------" << endl;
}
int main(int argc, char* argv[])
{
int a1[] = {2,4,9,16,19,68,78};
int a2[] = {4,8,67,106,109,115,120};
int a3[] = {9,15,19,108,119,130,190};
DoTest(
a1, sizeof(a1)/sizeof(a1[0]),
a2, sizeof(a2)/sizeof(a2[0]),
a3, sizeof(a3)/sizeof(a3[0]));
int a4[] = {2};
int a5[] = {120};
int a6[] = {130,190};
DoTest(
a4, sizeof(a4)/sizeof(a4[0]),
a5, sizeof(a5)/sizeof(a5[0]),
a6, sizeof(a6)/sizeof(a6[0]));
return 0;
}
Output
Array 1 -- 2 4 9 16 19 68 78
Array 2 -- 4 8 67 106 109 115 120
Array 3 -- 9 15 19 108 119 130 190
The top five -- 190 130 120 119 115
-----------------------
Array 1 -- 2
Array 2 -- 120
Array 3 -- 130 190
The top five -- 190 130 120 2
-----------------------
Press any key to continue . . .