5

I am looking for the most efficient algorithm to check if an array has a unique element in it. The result need not be the unique element, just true or false accordingly. I know I can reach O(n) efficiency with a hash table or somesuch, but I am still looking for a result which is more efficient space-wise, too.

e- the array is unsorted, and contains integers.

josh
  • 51
  • 3
  • Hi, the array contains integers. – josh Feb 20 '11 at 17:01
  • Yes, I forgot to add. It is an unsorted array, thanks. – josh Feb 20 '11 at 17:01
  • 1
    No, both are incorrect. I want to know if the array /has/ a unique element; it can have several unique elements, but I just want to know if it has one. That is, the algorithm is true for arrays such as {3,4,4,5} or {1,2,2} but false for {2,4,2,4}. (edit: looks like the comment I was responding to was deleted...) – josh Feb 20 '11 at 17:12
  • What range are these integers? If you could guarantee that the number of different values the integers can have is k, then I could give you a simple O(n)-time, O(k)-space algorithm. – David Grayson Feb 21 '11 at 04:47

4 Answers4

1

If the number of possible values is small and known in advance, you could use a bit array (which would be O(n) in time, O(n) in space, and would require less space than a hash table).

If the number of possible values is large, and you need this to be deterministic, then you could either use a hash table (which is O(n) if you have a good hash function and if you don't need to grow the hash table) or sort the list in place (which is O(n*lg(n) to sort, plus O(n) to search for the first unique element)

If the number of possible values is large, you do not need this to be deterministic, and if you want to see if a specific element is in the set, you could also use a Bloom Filter. A Bloom Filter is more space-efficient than a hash map, but there is a probability of false positives (the data structure thinks an element is in the set when it isn't)

NamshubWriter
  • 23,549
  • 2
  • 41
  • 59
0

I am not sure about O(n) but with O(n^2) you can take an element and keep it xor'ing with other elements

Neel Basu
  • 12,638
  • 12
  • 82
  • 146
  • XOR will give you the unique element iff the there's even # of the non-unique elements – kefeizhou Feb 20 '11 at 17:09
  • If you are happy with an O(n^2) algorithm, you might as well just compare each element with every other element. O(1) space, though, I guess. :-) – davidg Feb 20 '11 at 20:55
0

There is the function array_keys() in php.

array array_keys ( array $input [, mixed $search_value [, bool $strict = false ]] )

If the optional parameter $search_value is set, the function will only return the keys of the found values. if there is only on array key in return, so the value has to be unique.

I guess my answer is a little bit to (language) specific and i don't know the big-O of this function. You have to test it by yourself. :)

[Update]: I found this article which describes that array_keys() is O(n).

Community
  • 1
  • 1
derphil
  • 385
  • 6
  • 25
0

There are three different methods with different space and time complexities:

1) Two loops: time O(n^2), space O(1).

2a) Sort then linearly check : time O(nlogn) for the general case , space : O(1). 2b) Non comparison sorts (radix,counting,...) then check: time O(n), space O(n)

3) Hash table or array to store membership: time O(n), space O(n).

So basically, you should choose either 2a (space limit) or 3.

Binh Nguyen
  • 71
  • 1
  • 2