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：從列表中找到最低唯一整數

回答

相關問題