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.

Recommended Answers

All 9 Replies

Please post the full text of the error message.

Note: Exceptions are thrown when the code is executed, not by the compiler.

Thank you for responding, NormR1.

For the following code:

 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.


        //Use while loop to search for common elements between query array and collections array.
        while((queryCount < query.length) && (collectionsCount < collections.length))
        {
            comparisons++;  //Count comparisons.  This will be used in formula to ascertain run time for algorithm.
            if(query[queryCount] == collections[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((Comparable[])collections[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;

}

This is the exception that is being thrown.

Query is array 0
Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Integer; cannot be cast to java.lang.Integer
    at java.lang.Integer.compareTo(Integer.java:52)
    at CommonElements3.commonElements(CommonElements3.java:80)
    at TestCommonElements.main(TestCommonElements.java:19)

 ----jGRASP wedge2: exit code for process is 1.
 ----jGRASP: operation complete.

The problem lies in the following statement:

     else if(query[queryCount].compareTo((Comparable[])collections[collectionsCount]) < 0)

The method commonElements has to include Comparable[]. The argument of the method is taking an Object array. I adjust the statement from time to time, but normally, it will throw a Class Cast Exception. I am trying to find a workaround to this problem.

Thank you for taking the time to look this over.

java.lang.ClassCastException: [Ljava.lang.Integer; cannot be cast to java.lang.Integer

The [ character in [Ljava.lang.Integer refers to an array.
The compiler is complaining that the code is trying to cast an Integer object to an array of Integer objects.
The expression: collections[collectionsCount] is a single object, not an array.

Based on the data structure that I am using, I do not think I will be able to use the while loop. So here is the revised code.

    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.

            for( int i = 0; i < query.length; i++)
            {
                for(int j = 0; j < collections.length; j++)
                {
                    comparisons++;
                    if(query[i] == collections[j])
                    {
                        temp[match++] = query[i];
                        j++;

                    }
                }
            }


            Comparable[] intersection = new Comparable[match];
            System.arraycopy(temp, 0, intersection, 0, match);
            System.out.println(Arrays.deepToString(intersection));
            return intersection;

        }

I have one problem. I am probably overlooking something, but I cannot put my finger on it. I want to save the matches to a temporary array. When I run the test application, this information is generated.

Query is array 0
[]
[Ljava.lang.Comparable;@19ee1ac
Comparison:  12

The algorithm is linear, but I am getting an empty array. What am I doing wrong?

Thank you.

I am getting an empty array.

What is the variable name of the array, where does the code put anything into it and where are its contents printed out?

The array that I am trying to store the elements in is Comparable[] temp.

    if(query[i] == collections[j])
    {
        temp[match++] = query[i];
        i++;
        j++;
    }

This code is responsible for reassigning temp and then printing.

Comparable[] intersection = new Comparable[match];
System.arraycopy(temp, 0, intersection, 0, match);
System.out.println(Arrays.deepToString(intersection));
return intersection;

Where do you print the contents of temp itself?

Can you make a small complete program that compiles, executes and shows the problem.
The few lines of code you posted are not enough to show what could be happening in other parts of the program.

All right, NormR1. I think I have given up on the simple array linear solution for this data structure. What I am finding is that I need a deep transveral to review the subelements contained with each element of the data structure.

I am trying a hashSet. The code does find the common elements in linear time. I am just having trouble with casting the return statement of the common elements method. Hopefully, you can suggest what I can do to get around the class cast exception.

The revised code is as follows:

    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;
        private static Comparable[] intersection;

        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;

                    if(size < ((Comparable[])collections[indexOfLowest]).length)
                    {
                        indexOfLowest = i;
                    }

            }

            System.out.println("Query is array " + indexOfLowest);
            return indexOfLowest;  
        }

        public static Comparable[] commonElements(Object[] collections) 
        {

            int number = getIndexOfLowest(collections);  //Assign index to number. 

            Set commonElements = new HashSet();

            for(int i = 0; i < collections.length; i++)
            {
                Set hashSet = new HashSet(Arrays.asList(collections[number]));
                comparisons++;
                if(hashSet.contains(collections[i]))
                {
                    commonElements.add(collections[i]);
                }
            }

            Object[] collection = commonElements.toArray(new Object[0]);
            System.out.println(Arrays.deepToString(collection));
            return ((Comparable[]) collection);

        }


    }

The driver is as follows:

import java.util.*;
import java.util.Arrays;

public class TestCommonElements 
{

    public static void main(String[] args)
    {
        Integer[] collection1 = {1, 2, 3, 4, 5};
        Integer[] collection2 = {1, 2, 3, 4};
        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());

    }
}

This is the error that I am getting.

Query is array 1
[[1, 2, 3, 4]]
Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.Comparable;
    at CommonElements3.commonElements(CommonElements3.java:76)
    at TestCommonElements.main(TestCommonElements.java:19)

It doesn't like my cast to the return statement.

Thanks.

Try debugging by printing out the class and length of collection and collection[0]

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.