Link to home
Start Free TrialLog in
Avatar of shragi
shragiFlag for India

asked on

number common in 4 sorted arrays

I had a 4 arrays... I want to know the numbers common in all 4 arays...

my method.... run 4 for loops and verify each element....

for (int p=0; p<array1.len;p++)
{
   for (int j=0; j<array2.len;j++)  
    {
       if(array1[p]=array2[j])
       {
           for (int k=0; k<array3.len;k++)
             {
               if(array1[p]= array3[k]
              {
                  for (int m=0; m<array4.len;m++)
                   {
                      if (array1[p]= array4[m])
                      return array1[p];
                    }
               }
        }
}
}
}
}


but this not an effective method.... can some one suggest me an efficient method....
Avatar of for_yan
for_yan
Flag of United States of America image



this method displays common elements of two arraylists
http://www.roseindia.net/tutorial/java/collections/arraylist/displayCommonElement.html

you can fuirst do it for your arrays 1 and 2
then for arrays 3  and 4 and then
for the resulst of two previous steps
Avatar of a_b
a_b

Since it has to be common to all 4 arrays.
-> Pick a number in the first array and do a binary search in the other 3 arrays.
-> Another option is to use the count sort mechanism. Print out al numbers whose count is 4.
Didn't notice that they are sorted, anyway this
gives common elements for any four arrays:

Sure, if you have very long arrays, you want
to take that into account, otherwise it would work
in this way fine.

import java.util.ArrayList;

public class CommonIn4Arrays {

  public static int[] combineTwo(int[] a, int [] b){
      ArrayList<Integer> c = new ArrayList<Integer>();
      for(int j=0; j<a.length; j++){
          for(int jj=0; jj<b.length; jj++){
              if(a[j] == b[jj])c.add(a[j]);
          }
      }
   Object [] c1 = c.toArray();
      int[] c2 = new int[c1.length];
      for(int j=0; j<c1.length; j++){
            c2[j] = (Integer)c1[j];
      }
    return c2;
  }

    public static void main(String[] args) {
        int [] a = {1,2,8,15,19,20};
        int [] b = {1,2,13,15,19,20, 23};
         int [] c = {-5,3,2,13,15,19,22, 23,27};
        int [] d = {13,18,19, 20, 21,23,37};

        int [] ab = combineTwo(a,b);
        int [] cd = combineTwo(c,d);
        int [] abcd = combineTwo(ab,cd);
        for(int i: abcd){
            System.out.println(i);
        }


    }

}

Open in new window

Ouput:
19

Open in new window

ASKER CERTIFIED SOLUTION
Avatar of for_yan
for_yan
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of ozo
Your original method is actually not that bad, if you use the fact that the arrays are sorted so that you don't have to always restart each index at 0 or go all the way to the end.
but a conceptually simpler method could be to start with a routine that takes two sorted lists and returns a sorted list of the items in common, and use that to build a routine that does it for four sorted lists.