Write a program to find out the maximum 5 distinct elements from the 3 given array . For example if we are given three array as follows :
a[] = { 3, 1, 6, 7, 8, 9 };
b[] = { 10, 11, 6, 7, 2, 8 };
c[] = { 4, 5, 1, 8, 9, 2 };
then the output should be 11,10,9,8,7 as these are maximum 5 elements from the given 3 arrays.
Algorithm :
1) Sort all the three Array using Merge Sort or Quick or Heap Sort .
2) Repeat the below steps until find out the 5 max element.
3) Now find the maximum element form the three array by comparing last element of three array .
1) Insert element into the result[] array only if
1.1) the element is the first element to be insert in the result[] array .
1.2 ) the element is not similar to the previous element of result[]t array .
2) Else do not increment the result array index .
Implementation :
Time Complexity : O(nlogn) because of only merge sort .
Note : Above program work only if the distinct 5 max element are present int the three array . It can be easily enhanced for any other condition as well.
Please comment if you like the above post or if you find any mistake or if you have another way of solving the question .
a[] = { 3, 1, 6, 7, 8, 9 };
b[] = { 10, 11, 6, 7, 2, 8 };
c[] = { 4, 5, 1, 8, 9, 2 };
then the output should be 11,10,9,8,7 as these are maximum 5 elements from the given 3 arrays.
Algorithm :
1) Sort all the three Array using Merge Sort or Quick or Heap Sort .
2) Repeat the below steps until find out the 5 max element.
3) Now find the maximum element form the three array by comparing last element of three array .
1) Insert element into the result[] array only if
1.1) the element is the first element to be insert in the result[] array .
1.2 ) the element is not similar to the previous element of result[]t array .
2) Else do not increment the result array index .
Implementation :
public class Max5Element {
public static void main(String args[])
{
int a[] = { 3, 1, 6, 7,
8, 9 };
int b[] = { 10, 11, 6,
7, 2, 8 };
int c[] = { 4, 5, 1, 8,
9, 2 };
int len = a.length;
mergeSort(a,
0, len - 1);
mergeSort(b,
0, len - 1);
mergeSort(c,
0, len - 1);
for(int m=0;m<b.length;m++)
{
System.out.print(b[m]+" ");
}
findingMax5Element(a,
b, c);
}
private static void findingMax5Element(int[] a, int[] b, int[] c) {
int result[] = new int[5];
int lenA = a.length-1;
int lenB = b.length-1;
int lenC = c.length-1;
int i = 0;
//finding max
element form all the array
//and then
inserting it into the result[] array
while (lenA >= 0
&& lenB >= 0 && lenC >= 0 && i<5) {
int temp;
if (a[lenA] >=
b[lenB] && a[lenA] >= c[lenC]) {
temp
= a[lenA];
lenA--;
}
else if (b[lenB] >=
a[lenA] && b[lenB] >= c[lenC]) {
temp
= b[lenB];
lenB--;
}
else {
temp
= c[lenC];
lenC--;
}
// As we have to find the first distinct 5
max element
// We will compare the 'temp' to the
result[i-1] whether they are distinct or same
if(i==0)
{
result[i]=temp;
i++;
}
else if(i>0 &&
temp!=result[i-1])
{
result[i]=temp;
i++;
}
}
//printing max5
element
for(int j=0;j<5;j++)
{
System.out.print(result[j]+" ");
}
}
//below is merge
sort program
private static void mergeSort(int[] array, int first, int last) {
// TODO Auto-generated
method stub
if (first < last) {
int mid=(first+last)/2;
mergeSort(array,first,mid);
mergeSort(array,mid+1,last);
merge(array,first,mid,last);
}
}
private static void merge(int[] array, int first, int mid, int last) {
// TODO Auto-generated
method stub
int i=first;
int j=first;
int k =mid+1;
int len=array.length;
int temp[] = new int[len];
while(i<=mid &&
k<=last )
{
if(array[i]<array[k])
{
temp[j]=array[i];
j++;
i++;
}
else
{
temp[j]=array[k];
j++;
k++;
}
}
while(i<=mid)
{
temp[j]=array[i];
j++;
i++;
}
while(k<=last)
{
temp[j]=array[k];
j++;
k++;
}
for(int m=first; m <j
;m++ )
{
array[m]=temp[m];
}
}
}
Time Complexity : O(nlogn) because of only merge sort .
Note : Above program work only if the distinct 5 max element are present int the three array . It can be easily enhanced for any other condition as well.
Please comment if you like the above post or if you find any mistake or if you have another way of solving the question .
No comments:
Post a Comment