如果数据结构可以在适当位置进行突变并支持随机访问，则可以在O（N）时间和O（1）额外空间中进行操作。只需按顺序遍历该数组，并为每个索引将索引处的值写入由value指定的索引，然后将该位置的任何值递归地放置到该位置，并丢弃值>N。其中value与索引不匹配-
这是不在数组中的最小值。这样最多可以进行3N比较，并且仅使用一些值的临时空间。

# Pass 1, move every value to the position of its value
for cursor in range(N):
    target = array[cursor]
    while target < N and target != array[target]:
        new_target = array[target]
        array[target] = target
        target = new_target

# Pass 2, find first location where the index doesn't match the value
for cursor in range(N):
    if array[cursor] != cursor:
        return cursor
return N