Python：从列表中找到最低唯一整数

我想从列表中找出最低唯一元素。我已经能够生成O（n^2）和O（n）解决方案。但我没有发现他们优化。请帮助我理解，如果有可能的O（n）解决方案。 请勿使用任何衬垫解决方案。下面是我的代码：Python：从列表中找到最低唯一整数

主要功能：

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

我想避免使用MAX（阵列）在上面的解决方案。

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]

来源

2016-12-26 AN_SH

所以你不能使用min（）？ –

我们必须得到最低的唯一编号。使用min，我们会得到-6，但它不是唯一的。 –

您可以尝试对列表进行排序，然后将每个数字与下一个数字进行比较？或者这会被认为是一种线性解决方案？ –

我不能，因为它取决于执行的大O置评内置的，我从来没有看着蟒蛇功能。这里有一个更合理的实现：

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

来源

2016-12-26 02:22:33

Python：从列表中找到最低唯一整数

回答

相关问题