如果数据结构可以在适当位置进行突变并支持随机访问，则可以在O（N）时间和O（1）额外空间中进行操作。只需按顺序遍历该数组，并为每个索引将索引处的值写入由value指定的索引，然后将该位置的任何值递归地放置到该位置，并丢弃值>N。其中value与索引不匹配-
这是不在数组中的最小值。这样最多可以进行3N比较，并且仅使用一些值的临时空间。
# Pass 1, move every value to the position of its valuefor 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 valuefor cursor in range(N): if array[cursor] != cursor: return cursorreturn N
