I am trying to develop a method that can find common elements in a simple array with a linear run time O(n + m). This is an old school problem, i.e., no hashsets, hashtables, arraylists. Here is what I have so far.
import java.util.*;
import java.util.Arrays;
public class CommonElements3
{
private static int comparisons = 0;
private static Object[] collections;
private static Object[] match;
private static Comparable[] temp; /*Current array being traversed.*/
private static Object[] common = new Comparable[20];
private static int counter = 0;
private static int number;
public static int getComparisons()
{
return comparisons;
}
public void setComparisons(int comparisons)
{
this.comparisons = comparisons;
}
public static Comparable getNumber()
{
return number;
}
public static int getIndexOfLowest(Object[] collections) //Use this method to obtain array for query.
{
int indexOfLowest = 0; //Declare number variable.
int count = 0; //Declare count variable.
int size = 0; //Declare size variable.
/*locate smallest array for query.*/
for(int i = 0; i < collections.length; i++)
{
Arrays.sort((Comparable[])collections[i]);
size = ((Comparable[])collections[i]).length - 1;
int miniNumber = ((Comparable[]) collections[indexOfLowest]).length - 1;
if(miniNumber > size)
{
indexOfLowest = size;
}
}
System.out.println("Query is array " + indexOfLowest);
return indexOfLowest;
}
public static Comparable[] commonElements(Object[] collections)
{
int queryCount = 0; //Declare queryCount variable.
int collectionsCount = 0; //Declare collectionsCount variable.
int match = 0; //Declare match variable.
int number = getIndexOfLowest(collections); //Assign index to number.
Comparable[] query = ((Comparable[]) collections[number]); //Assign array collections[number] to Comparable[] query.
Comparable[] temp = new Comparable[collections.length]; //Declare Comparable[] temp array.
Comparable[] compCollection = ((Comparable[]) collections[collections.length]); //Cannot cast Object to Comparable****
//Use while loop to search for common elements between query array and collections array.
while((queryCount < query.length) && (collectionsCount < compCollection.length))
{
comparisons++; //Count comparisons. This will be used in formula to ascertain run time for algorithm.
if(query[queryCount] == compCollection[collectionsCount]) //Compare elements in arrays.
{
temp[match++] = query[queryCount]; //Add match to temporary array.
queryCount++; //Increment queryCount.
collectionsCount++; //Increment collectionsCount.
}
else if(query[queryCount].compareTo(compCollection[collectionsCount]) < 0) //Another area where compiler throws a Class Cast Exception.
{
queryCount++; //Increment queryCount.
}
else
{
collectionsCount++; //Increment collectionsCount.
}
}
Comparable[] intersection = new Comparable[match];
System.arraycopy(temp, 0, intersection, 0, match);
System.out.println(Arrays.deepToString(intersection));
return intersection;
}
}
The compiler will throw Class Cast Exception where I try to cast Object to Comparable in the commonElements method. I know that Object is the root of all classes, and I know why the compiler is doing this. However, is there a workaround to this. Also, is this a good algorithm for the test data below?
import java.util.*;
import java.util.Arrays;
public class TestCommonElements
{
public static void main(String[] args)
{
Integer[] collection1 = {1, 2, 3, 4};
Integer[] collection2 = {1, 2, 3, 4, 5};
Integer[] collection3 = {1, 2, 3, 4, 5, 6, 7, 8};
Integer[] collection4 = {1, 2, 3, 4, 6};
Object[] storeAllArray = {collection1, collection2, collection3,};
System.out.println(CommonElements3.commonElements(storeAllArray));
System.out.println("Comparison: " + CommonElements3.getComparisons());
}
}
I like the O(n + m) approach for the commonElements method, but in this case, I may have to use a nested for loop O(n*m + n) because of the data structure in the test application. Any advice is greatly appreciated.