CODEWITHSUNDEEP
javaloopsexceptionconcurrentmodification
Legato
Legato

Reputation: 610

Removing all non-unique members of a list

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?

Upvotes: 0

Views: 133

Answers (3)

Apoorv
Apoorv

Reputation: 1101

With Java 8, you can do what Mshnik is doing using the stream API. However, as this is still a new API, you may want to use this with a bit of caution at work. Readability (by you as well as your peers) should triumph over conciseness. If using Java 8/stream API is not an option then Mshnik's solution is what I'd go with.

List<Integer> uniques = 
    list.stream().
         collect(Collectors.groupingBy(i -> i, Collectors.reducing(0, (a, b) -> a + b))). //Adding all occurances of that number {3->6, 5->5, 8->16, 2->2}
         entrySet().stream(). //The above map's entries as a set
         filter(e -> e.getValue() == e.getKey()). //Retains {5->5, 2->2}
         map(e -> e.getKey()). //Retains {5, 2}
         collect(Collectors.<Integer>toList()); //Collects

Note that while each line may seem as another iteration over the list, this is actually a 2-pass solution (first pass is when we collect as map and the second pass when we collect the list).

Complexity: expected O(N) --as the groupingBy would use a HashMap.

Upvotes: 1

Mshnik
Mshnik

Reputation: 7032

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;
}

Upvotes: 4

Elliott Frisch
Elliott Frisch

Reputation: 201447

I suggest you start with a method to count the number of times an item appears in a List. Something like

private static <T> int count(List<T> al, T val) {
    int r = 0;
    for (T t : al) {
        if (t.equals(val)) {
            r++;
        }
    }
    return r;
}

Then create a new List to return, and check the count is 1 before you add it to that List like

private static List<Integer> getUniques(List<Integer> list) {
    List<Integer> al = new ArrayList<>();
    for (Integer n : list) {
        if (count(list, n) == 1) {
            al.add(n);
        }
    }
    return al;
}

Upvotes: 1

Related Questions