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;
}
| improve this answer | |
\$\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.)

| improve this answer | |
\$\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);
}
| improve this answer | |
\$\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.

| improve this answer | |
\$\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.