number common in 4 sorted arrays

shragi
shragi used Ask the Experts™
on
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....
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Awarded 2011
Awarded 2011

Commented:


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
a_b
Top Expert 2009

Commented:
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.
Awarded 2011
Awarded 2011

Commented:
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

Awarded 2011
Awarded 2011
Commented:


this gives alorithm of finding common elements in tqwo sorted arrays:
http://stackoverflow.com/questions/4529819/finding-common-elements-in-two-arrays-of-different-size

In combination with the above method it will gicve you reasonable efficinecy - you'll probably also have to sort
intermeidtae pairwise arrays.
ozo
Most Valuable Expert 2014
Top Expert 2015

Commented:
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.

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial