Python: Finding Lowest Unique Integer from List

Question

I am trying to find out lowest unique element from list. I have been able to generate O(n^2) and O(n) solutions. But I don't find them optimized. Kindly help me understand,if there is a possible O(n) solution for it. No one liner solutions please. Below are my codes:

Main function:

if __name__ =="__main__":
    print uniqueMinimum([6, 2, 6, -6, 45, -6, 6])
    print lowestUnique([5, 10, 6, -6, 3, -6, 16])

O(n^2) Solution:

def lowestUnique(arr):
     num = max(arr)
     for i in range(len(arr)):
         check  = False
         for j in range(len(arr)):
             if arr[i]==arr[j] and i!=j:
                 check =True
             if check==False:
                 if num > arr[i]: 
                      num = arr[i]
     return num

I would like to avoid using max(array) in above solution.

O(n) Solution:

def uniqueMinimum(array):
     d ={}
     a =[]
     num = max(array)
     for i in range(len(array)):
         k =d.get(array[i])
         if k is None:
             d[array[i]] = 1
             a.append(array[i])

         else:
             d[array[i]] = k+1
             if array[i] in a:
                 a.remove(array[i])

     a.sort()
     return a[0]

We have to get lowest unique number. Using min, we will get -6,but its not unique. — AN_SH
– AN_SH, Commented Dec 26, 2016 at 2:04
Can you try sorting the list and then comparing each number to the next one? Or would that be considered a linear solution? — Pike D.
– Pike D., Commented Dec 26, 2016 at 2:16
If we sort, array will be, [-6, -6, 2, 6, 6, 6, 45]. if we compare if a[i] == a[i+1] and i !=j, result will be -6 only as a[1] =-6 and a[2]=2. — AN_SH
– AN_SH, Commented Dec 26, 2016 at 2:26

Ryne Everett · Accepted Answer · 2016-12-26 02:22:33Z

1

I can't really comment on the big-O since it depends on the implementation of the built-in python functions which I've never looked into. Here's a more reasonable implementation though:

def lowestUnique(array):
    for element in sorted(list(set(array))):
        if array.count(element) == 1:
            return element
    raise Exception('No unique elements found.')

answered Dec 26, 2016 at 2:22

Ryne Everett

6,9293 gold badges40 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Python: Finding Lowest Unique Integer from List

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related