现代社会中，有很多服务依赖⼀种被称为ID的概念。例如⾝份证就是⼀种ID，银⾏账户也是⼀种ID，电话号码本质上也是⼀种ID。假设我们使⽤⾮负整数作为某个系统的的ID，所有⽤户都由⼀个ID唯⼀确定。任何时间，这个系统中有些ID处在使⽤中的状态，有些ID则可以⽤于分配给新⽤户。现在的问题是，怎样才能找到最⼩的可分配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(n²)

代码

<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)，再循环遍历标记数组，输出第一个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>

解法四

思路

解法四思路