Re: Best way to check if all elements in a List are unique

On Mon, 1 Mar 2010, John B. Matthews wrote:


I am tickled that we've all thought of exactly the same solution! Are
there any other interesting ways to do this?

The only improvement, of sorts, i'd offer is:

boolean areAllUnique(List<T> l) {
  Set<T> seen = new HashSet<T>();
  for (T o: l) if (!seen.add(0)) return false;
  return true;
}

Which doesn't need to examine any more elements of the list than it
absolutely has to to decide if the list is all unique. Except for zero-
and one-element lists, that is.

The way i'd do this in shell script is (not tested!):

l="space separated list"
[[ $(echo $l | wc -w) -eq $(echo $l | tr ' ' '\n' | sort -u | wc -w) ]]

Which suggests the following java:

boolean areAllUnique(List<T> l) {
  l = new ArrayList<T>(l);
  Collections.sort(l);
  T prev = null;
  for (T cur: l) {
  if (cur.equals(prev)) return false;
  prev = cur;
  }
  return true;
}

Which is pretty different, but still built around the idea of sorting and
then detecting duplicates by comparing adjacent elements, as sort -u does.

tom

--
Virtually everything you touch has been mined. -- Prof Keith Atkinson