Can Two Sets Be Checked for Equality in Less Than O(nlogn) Time?

[daniel_i_l]

Let's say I have an unsorted array of integers. Is it possible to determine if there exists a number in the array that appears only once with a time complexity of less than O(nlogn)? Sorting the array takes nlogn time so I'm wondering if it's possible without sorting. I don't need to return the element, only to determine that it exists.

I think that the answer is no. If it was possible than it'd also be possible to check if two sets are equal or not in less that nlogn time since you could simply connect the sets and check if there's a unique element. Does anyone know the best algorithm for checking if two sets are equal?
Thanks,
Daniel

 

[rcgldr]

Depends on the range of integer values versus the size of the available memory. For 32 bit integers, you'd need 4GB of 2 bit fields which would require 1GB of memory, something that would be available on most PC's these days.

You'd start off with a zeroed out array of 2 bit fields. You'd then make a single pass over the array of integers, using the integer value as an index into the array of 2 bit fields. If it's the first occurence, the bit field value will be 0 and you change it to 1. If it's not the first occurence, then the bit field value will be non-zero and you change it to an 2 (if it's already 2, you don't need to change it).

After you're done, you make a single pass on the array of bit fields, and output the index of every instance where the value is 1.

update This process would take n + 4GB steps. If n is relatively small, then it would be better to use a n(log(n)) type algorithm. Sorting in ram is fairly fast.

If you don't need to know the values of the unique number(s) in the array, then you can just use a counter that is incremented every time you find a "first occurence" and decremented every time you find a "second" occurence, and not modified if you find a 3rd or more occurance (2 bit field already set to 2). This process would only take n steps.

 

[mXSCNT]

This might be faster than sorting:

def hasuniq(list):
  hashmap = {}
  unmatched = 0
  for x in list:
    if x in hashmap:
      if hashmap[x] == True:
        unmatched -= 1
        hashmap[x] = False
    else:
      unmatched += 1
      hashmap[x] = True
  return unmatched > 0

The precise time complexity of this depends on the size of your hashtable and assumes that the values don't hash pathologically, but if you wrote it in C it could probably be made faster for most cases than the equivalent sort in C.

Really though, n log n (by sorting) is going to be fast enough. log n is almost a constant time factor difference, for practical input sizes.