Remove duplicate elements from array along with element using Java 1.7

Question

I need to write a method where a int[] will be supplied as an input and it should return an array, but with all of the numbers that occur more than n times removed entirely.

Input:

(int list) data = [1, 2, 2, 3, 3, 3, 4, 5, 5]

Output:

(int list) [1, 4]

These are the steps i have tried:

• Copy the int array to ArrayList (inputList).
• Create a LinkedHashset to find unique values
• Iterate LH and find the collection frequency of ArrayList with iterator.

    int[] intArray = new int[0];
ArrayList<Integer> inputList = new ArrayList<Integer>(data.length);
        //System.out.println(Arrays.toString(data));
        for (int i = 0; i < data.length; i++){
            inputList.add(Integer.valueOf(data[i]));
        }

        LinkedHashSet<Integer> lhs = new LinkedHashSet<>(inputList);

        intArray = new int[lhs.size()];
        int i=0;
        int j=0;
        Iterator<Integer> itr = lhs.iterator();
        while(itr.hasNext()){
            Integer shiftNumber = itr.next();

            if(Collections.frequency(inputList, shiftNumber)==1) {
                intArray[i++] = shiftNumber.intValue();
                j++;
            }


        }
        intArray = Arrays.copyOf(intArray, j);
        return intArray;
    }
}

return intArray;

I am able to achieve the results with the above snippet.However, I need suggestions in reducing the piece of code and improving performance by using any algorithms or other collection objects.

Answer 1

Use the right tools

You are on the right track to use Collections.frequency, as it does a lot of the plumbing for you

Start simple

The basic idea is to create a new list, unique that will contain the numbers that are unique.

This is the piece of code that will do all the hard work (but is not optimized yet!).

ArrayList<Integer> uniqueNumbers = new ArrayList<>();

for (Integer number : numbers) {
    if (Collections.frequency(numbers, number) == 1) {
        uniqueNumbers.add(number);
    }
}

Now you only need to convert your input array to an numbers ArrayList and convert the resulting uniqueNumbers list back to an array.

Then optimize

If you care about performance, you will probably want to skip number that you have already checked and know that they are non unique. You can do this with a Set<Integer>.

Set<Integer>  nonUniqueNumbers   = new HashSet<>();
ArrayList<Integer> uniqueNumbers = new ArrayList<>();

for (Integer number : numbers) {

    if (!nonUniqueNumbers.contains(number)) {
        if (Collections.frequency(numbers, number) == 1) {
            uniqueNumbers.add(number);
        }
        else {
            nonUniqueNumbers.add(number)
        }
    }
}

More room for performance

To increase the performance, you only want to scan each input element once; this can for example be done like this:

public static Collection<Integer> getUniques( Collection<Integer> input )
{
    Set<Integer> uniques = new HashSet<>();
    Set<Integer> nonUniques = new HashSet<>();
    for ( Integer i : input )
    {
        //if i is in the nonUnique set, we already have it twice, 
        //no need to do anything with it anymore
        if ( nonUniques.contains( i ) )
        {
            continue;
        }
        else
        {
            //either we never saw i, or we have seen it once.
            //if we saw it once, it will be in the uniques.
            if ( uniques.contains( i ) )
            {
                //if it was in the uniques , this is the second time we encountered it.
                //remove it from the uninques and put it in the nonUniques
                uniques.remove( i );
                nonUniques.add( i );
            }
            else
            {
                //if we never saw i, it should be in the uniques set (for now)
                uniques.add( i );
            }
        }
    }
    return uniques;
}