現代社會中，有很多服務依賴?種被稱為ID的概念。例如?份證就是?種ID，銀?賬戶也是?種ID，電話號碼本質上也是?種ID。假設我們使??負整數作為某個系統(tǒng)的的ID，所有?戶都由?個ID唯?確定。任何時間，這個系統(tǒng)中有些ID處在使?中的狀態(tài)，有些ID則可以?于分配給新?戶?，F在的問題是，怎樣才能找到最?的可分配ID呢？例如下?的列表記錄了當前正在被使?的ID：
[18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6]
最?可分配的ID，也就是不在這個列表中的最?整數是10
解法一：
思路
因為是求最小可用ID，可遞歸枚舉ID，這個過程是O(n),枚舉的ID，若該ID?列表，則該ID為最小可分配的ID，判斷一個元素屬不屬于一個列表，這一過程是O(n)。綜上，算法時間復雜度為O(n2)
代碼
<pre><code>
def Min_Free(lst):
n = len(lst)
for i in xrange(0,n):
if i not in lst:
return i
</code>
</pre>
解法二：
思路
開辟一個標記數組，標記列表元素對應的位置為TRUE，這一個過程時間為O(n)，再循環(huán)遍歷標記數組，輸出第一個FALSE對應的索引，即為最小可分配ID，這一過程時間為O(n)。綜上，該算法時間復雜度為O(n)
代碼
<pre><code>
def Min_Free2(lst):
n = len(lst)
marked = [False]*(n+1)
for elem in lst:
if elem<n:
marked[elem] = True
for i in xrange(0,n):
if marked[i] ==False:
return i
</code></pre>
<p>上述代碼只是為了分析時間復雜度更清晰，為了代碼的簡潔，作如下修改</p>
<pre><code>
def Min_Free2_1(lst):
n = len(lst)
marked = [False]*(n+1)
for elem in lst:
if elem<n:
marked[elem] = True
return marked.index(False)
</code></pre>
解法三
思路
借助快排，時間復雜度為O(nlgn),排序后，在看元素的值和索引是否相同，若不同則返回該元素的索引。
代碼
<pre><code>
def Min_Free3(lst):
lst = sorted(lst)
n = len(lst)
for i in range(0,n):
if lst[i]!=i:
return i
</code></pre>
解法四
思路
