3
\$\begingroup\$

I am trying to find the uncommon elements from two sets in Java. Here is my way:

private void findUnCommon{

    Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3, 4));
    Set<Integer> b = new HashSet<>(Arrays.asList(3, 4, 5, 6));
    // get all elements from set a and set b

    System.out.println("Before..");
    System.out.println("a is : " + a);
    System.out.println("b is : " + b);

    Set<Integer> result = new HashSet<>(a);
    result.removeAll(b);
    System.out.println("result is : " + result);

    Set<Integer> temp = new HashSet<>(b);
    temp.removeAll(a);
    System.out.println("temp is : " + temp);

    result.addAll(temp);
    System.out.println("Uncommon elements of set a and set b is : "
        + result);

    System.out.println("After..");
    System.out.println("a is : " + a);
    System.out.println("b is : " + b);
}

I have declared two extra sets. Can this be improved?

\$\endgroup\$
10
\$\begingroup\$

Is this a method? You can't just plop code anywhere in Java.

The name of the operation is symmetric difference, so you should probably call it that.

Here's a more compact implementation.

private Set<T> symmetricDifference(Set<T> a, Set<T> b) {
    Set<T> result = new HashSet<T>(a);
    for (T element : b) {
        // .add() returns false if element already exists
        if (!result.add(element)) {
            result.remove(element);
        }
    }
    return result;
}
\$\endgroup\$
  • \$\begingroup\$ Now the above method will generate syntactical error for generic variable T. So change the method declaration to be like private <T> Set<T> symmetricDifference(Set<T> a, Set<T> b) {...} \$\endgroup\$ – Vivek Apr 2 '18 at 3:26
  • \$\begingroup\$ @Vivek If the type variable T is introduced when the class is defined, it works as written. \$\endgroup\$ – 200_success Apr 2 '18 at 3:50
7
\$\begingroup\$

With Apache Commons Collections (javadoc):

CollectionUtils.disjunction(a, b);

With Guava (javadoc):

Sets.symmetricDifference(a, b);

See also: Effective Java, 2nd edition, Item 47: Know and use the libraries (The author mentions only the JDK's built-in libraries but I think the reasoning could be true for other libraries too.)

\$\endgroup\$
3
\$\begingroup\$

This should work faster:

private void findUnCommon{

    Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3, 4));
    Set<Integer> b = new HashSet<>(Arrays.asList(3, 4, 5, 6));

    Set<Integer> result = new HashSet<>();
    for (Integer el: a) {
      if (!b.contains(el)) {
        result.add(el);
      }
    }
    for (Integer el: b) {
      if (!a.contains(el)) {
        result.add(el);
      }
    }
    System.out.println("Uncommon elements of set a and set b is : "
        + result);
}
\$\endgroup\$
0
\$\begingroup\$

If data is ordered, as is the case in your example, you can use a merge-sort algorithm to do it while traversing each collection only once:

    List<Integer> a = Arrays.asList(1, 2, 3, 4);
    List<Integer> b = Arrays.asList(3, 4, 5, 6);
    List<Integer> result = new ArrayList<>();

    int ia = 0, ib = 0;

    while(ia<a.size() && ib<b.size()) {
        if (a.get(ia)<b.get(ib)) {
            result.add(a.get(ia));
            ia++;
        } else if (a.get(ia)>b.get(ib)) {
            result.add(b.get(ib));
            ib++;
        } else {
            ia++;
            ib++;
        }
    }
    result.addAll(a.subList(ia, a.size()));
    result.addAll(b.subList(ib, b.size()));

    System.out.println("Uncommon elements of set a and set b is : " + result);

If an actual java.util.Set is required, instead of any collection that in this case behaves as a set, one may use a java.util.SortedSet implementation (e.g., java.util.TreeSet). The code above can be directly translated to iterators by using a PeekableIterator wrapper. Without peek(), it requires a little more effort to advance each iterator only when needed.

\$\endgroup\$
  • \$\begingroup\$ HashSets are never ordered, even if parameter lists in their constructors are. \$\endgroup\$ – Alexei Kaigorodov Oct 5 '13 at 18:34
  • \$\begingroup\$ The question seems to be about sets in general, not specifically about hashing (check the title). Sets can be represented with ordered data structures and I was precisely pointing out the usefulness of doing so here. I changed my reply to emphasize that the assumption is on the data, not on HashSets. \$\endgroup\$ – jop Oct 5 '13 at 20:10

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .