The minimum unique number in an array is defined as
min{v|v occurs only once in the array}
For example, the minimum unique number of {1, 4, 1, 2, 3} is 2.
Is there any way better than sorting?
-
"Better" meaning "lower time complexity"?Vaughn Cato– Vaughn Cato2012-08-14 01:57:58 +00:00Commented Aug 14, 2012 at 1:57
-
@VaughnCato:yes, I wonder if we can do better than O(nlogn).shilk– shilk2012-08-14 02:00:38 +00:00Commented Aug 14, 2012 at 2:00
-
Is the range of your values limited or restricted? If they are integral with a restricted range, I believe O(N) is possible.walrii– walrii2012-08-14 02:04:45 +00:00Commented Aug 14, 2012 at 2:04
-
@walrii: The element can be any integer. But feel free to show your solution with the constraints you mentioned above.shilk– shilk2012-08-14 02:25:53 +00:00Commented Aug 14, 2012 at 2:25
Add a comment
|
3 Answers
I believe this is an O(N) solution in both time and space:
HashSet seenOnce; // sufficiently large that access is O(1)
HashSet seenMultiple; // sufficiently large that access is O(1)
for each in input // O(N)
if item in seenMultiple
next
if item in seenOnce
remove item from seenOnce
add to item seenMultiple
else
add to item seeOnce
smallest = SENTINEL
for each in seenOnce // worst case, O(N)
if item < smallest
smallest = item
If you have a limited range of integral values, you can replace the HashSets with BitArrays indexed by the value.
10 Comments
ElKamina
This is all great sir, but where can I find this magical O(1) random access hash function you speak of? As far as I (and the rest of the world) know the "best" random access time for hash function is O(logn).
DSM
Unless I'm missing something, no random access is needed. The first pass loops over
input (O(N)) and does lookups, insertions, and deletions on the hash sets, each O(1). Total: O(N). The second pass as written currently loops over seenOnce, but that's easily fixed: simply loop over input again (O(N)), test membership in seenOnce (O(1)), and if it's there append it to a new seenOnceList (O(1)), total O(N). Finally do a scan for the minimum, O(N). Net O(N), no?
walrii
@ElKamina - You are confusing a tree with a hash. See en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions and look at the list under O(1). With a large table and an appropriate hash function, collisions are insignificant.
walrii
@DSM - my loop over seenOnce is what you called "a scan for the minimum". What is the purpose of the extra loop you added?
walrii
@DSM - The advantage of the array optimization is that the hash function = I() and no collision handling is needed. No Big-O advantage, granted, but simpler and faster.
|
You don't need to do full sorting. Perform bubble sort inner loop until you get distinct minimum value at one end. In the best case this will have time complexity O(k * n) where k = number of non-distinct minimum values. However worst case complexity is O(n*n). So, this can be efficient when expected value of k << n.
I think this would be the minimum possible time complexity unless you can adapt any O(n * logn) sorting algorithms to the above task.
Comments
Python version using dictionary.
Time complexity O(n) and space complexity O(n):
from collections import defaultdict
d=defaultdict(int)
for _ in range(int(input())):
ele=int(input())
d[ele]+=1
m=9999999
for i in d:
if d[i]==1 and i<m:
m=i
print(m if m!= 9999999 else -1)
Please tell me if there is a better approach.
