Geek asks and answers

Finding the minimum unique number in an array

The minimum single number in the array is defined as        min{v|v occurs only once in the array} For example, the minimum unique number {1, 4, 1, 2, 3} is 2. Is there a better way to sort?

+5
source share
2 answers

I believe this solution is O (N) both in time and in 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 HashSets with BitArrays indexed by value.

+5
source

. , . O (k * n), k = . O (n * n). , , k < .

, , O (n * logn) .

0

More articles:


All Articles