如何找到不在給定數組中的時間複雜度較低的最小正整數？

-5

給定一個數組，如何計算出具有高性能的Minial正整數（不考慮內存使用），並且該整數不應該在數組中，並且在給定數組中可能存在重複的正數和負數。如何找到不在給定數組中的時間複雜度較低的最小正整數？

例如，給定的數組：

殼體1：

when l = [-4, 7, 2, 2, 2, 3, 3, 4] 
return 1

殼體2：

when l = [-3, -9, 1, 2, 3, 7, 5] 
return 4

我曾嘗試這樣的（Python代碼）：

def find_min_not_in(l): 
    min = -sys.maxint 
    for i in l: 
     min = i if i > 0 and i < abs(min) 
    if min <= 0 or min >= 2: 
     return min = 1 
    while min in l: 
     min = min+1 
    return min

但它不是最好的，因爲in op正在一次又一次掃描整個陣列。我想要一個低時間複雜性解決方案。

來源

2016-09-19 fandyst

請出示你的研究/調試工作至今。請先閱讀[問]頁面。 –

對不起，但經過4年多的時間，我預計會有一個_better_問題，你不覺得嗎？ –

不僅如此，你應該校對你的問題。拼寫錯誤（「重複性」）。「不在數組中」......你的意思是「不在數組中」嗎？並請澄清「高性能」。內存使用情況還是運行時間？在考慮優化之前，您應該先制定一個可行的解決方案。 – Joe

我不知道這是一個更高性能的解決方案，但我使用了集合理解和設置操作的組合，這通常很快。第一行創建一個刪除重複項的列表。此外，還有一個條件是隻在該列表中創建具有正整數的集合。第二種說法會在該範圍內的數字與您的列表之間產生差異。這比排序快，因爲排序需要n^2次，而創建時間是n次。由於我們不關心重複值，所以我們可以使用set方法。

lis_1 = [-4, 7, 2, 2, 2, 3, 3, 4] 
lis_2 = [-3, -9, 1, 2, 3, 7, 5] 
def find_least_not_in(l): 
    s_l = {x for x in l if x > 0} 
    return min(set(range(1,max(s_l)+1)).difference(s_l)) 
print "Case 1: ", find_least_not_in(lis_1) 
print "Case 2: ", find_least_not_in(lis_2)

這裏是輸出，當我跑它：

=================== RESTART: C:/Users/Joe/Desktop/stack.py =================== 
Case 1: 1 
Case 2: 4 
>>>

來源

2016-09-19 07:26:52 Joe

如何找到不在給定數組中的時間複雜度較低的最小正整數？

回答

相關問題