Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Checking for a unique element

  1. Jul 13, 2009 #1

    daniel_i_l

    User Avatar
    Gold Member

    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
     
  2. jcsd
  3. Jul 13, 2009 #2

    rcgldr

    User Avatar
    Homework Helper

    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.
     
    Last edited: Jul 13, 2009
  4. Jul 13, 2009 #3
    This might be faster than sorting:
    Code (Text):

    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.
     
    Last edited: Jul 13, 2009
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Checking for a unique element
Loading...