Removing all non-unique members of a list

Question

I wanted to create a method that would filter out all non-unique members of a list, such that a list with an input

3 5 3 8 8 2

Would become

5 2

I had the idea to try the following:

private static List<Integer> getUniques(List<Integer> list) {
        for (Integer n : list) {
            list.remove(n);
            if (!list.contains(n)) {
                list.add(n);
            } else {
                while (list.contains(n)) {
                    list.remove(n);
                }
            }
        }
        return list;
    }

But this throws a Concurrent Modification exception. I made a working adjustment:

private static List<Integer> getUniques(List<Integer> list) {
        List<Integer> result = new ArrayList<>();
        Set<Integer> distinctSet = new HashSet<>();

        distinctSet.addAll(list);
        result.addAll(list);

        for (Integer n : distinctSet) {
            result.remove(n);
            if (!result.contains(n)) {
                result.add(n);
            } else {
                while (result.contains(n)) {
                    result.remove(n);
                }
            }
        }
        return result;
    }

This accomplishes what I want, but seems a bit convoluted/inefficient. Is there a way for me to do it the first way I had in mind? Or another more efficient method in general? Or am I already essentially using the best approach available?

Answer 1

A better approach is to use a HashMap to flag elements to keep, then add based on that. This approach is O(N), which is better than the O(N^2) of your solution (remove may be O(N), depending on the List implementation passed in). It also certainly preserves the ordering of the elements in the original list, if that is important.

private static List<Integer> getUniques(List<Integer> list) {
    HashMap<Integer, Boolean> flagMap = new HashMap<>();

    //Total Loop: O(N)
    for(Integer i : list){
        if(flagMap.containsKey(i)) flagMap.put(i, false); //O(1)
        else flagMap.put(i, true); //O(1)
    }

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

    //Total Loop: O(N)
    for(Integer i : list){
        if(flagMap.get(i)) result.add(i); //O(1)
    }
    return result;
}