Python:从列表中查找最低的唯一整数

问题描述

我试图从列表中找出最低的唯一元素.我已经能够生成 O(n^2) 和 O(n) 解决方案.但我发现它们没有优化.请帮助我理解，如果有可能的 O(n) 解决方案.请不要使用任何一种班轮解决方案.以下是我的代码:

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:

主要功能:

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

O(n^2) 解决方案:

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

我想避免在上述解决方案中使用 ma​​x(array).

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

O(n) 解决方案:

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]

推荐答案

我无法真正评论 big-O，因为它依赖于我从未研究过的内置 Python 函数的实现.不过，这是一个更合理的实现:

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.')

这篇关于Python:从列表中查找最低的唯一整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！