-->

Maximum 5 elements from 3 given Array

Posted by Admin on
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 : 

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