下面的函數是O（n）時間和O（1）空間，其中n = | A |？

Question

def firstMissingPositive(self, A): 
    least = 1024*1024*1024 
    # worst case n ops 
    for i in A: 
     if i < least and i > 0: 
      least = i 
    if least > 1: 
     return 1 
    else: 
     # should be O(n) 
     A_set = set(A) 
     # worst case n ops again 
     while True: 
      least += 1 
      if least not in A_set: 
       return least 

我只問，因爲它對於給定的問題似乎太簡單了，這裏的大多數人可能在Leetcode或類似的地方看過。在Python的set或dict的實現中有沒有我不知道的東西？查找應該是O（1），根據我的理解，將列表轉換爲集合應該是O（n）。

Answer 1

這不是O(1)空間，它是O(n)空間，因爲你需要構建集合。

至於時間，根據the Python wiki，設置遏制需要O(n)最壞的情況。所以你的算法是O(n^2)。請注意，這是最糟糕的情況 - 設置遏制的平均時間爲O(1)，因此算法的平均時間複雜度確實爲O(n)。

通過使用有序集，您可以將最差情況降至O(n log n)，但平均時間也將爲O(n log n)。