【数组】--第一个缺失的正整数

循环不变式

def swap(arr, s, t):
    tmp = arr[t]
    arr[t] = arr[s]
    arr[s] = tmp
# 利用循环不变式设计算法流程
# 非常重要一点，数组中舍弃一个数，将其与数组最后一个有效元素交换，数组有效元素减一即可，不用将其后元素依次前移。
def fisrtNull(arr):
    i = 0  # 指向当前处理元素
    t = len(arr) - 1  # 指向数组最后一个有效元素
    while i <= t:
        # 元素小于1，小于当前id即与前面重复，大于数组长度，都应该舍弃
        if arr[i] < (i+1) or arr[i] > len(arr):
            swap(arr, i, t)  # 与最后一个有效元素交换
            t -= 1  # 有限元素减一，此处t指向最后一个有效元素
        elif arr[i] > (i+1): # 大于当前id,但小于数组长度
            if arr[arr[i]-1] == arr[i]: # 后面相应位置已有此元素，舍弃
                swap(arr, s, t)
                t -= 1
            else: # 后面相应位置无此元素，将其交换到正确位置上
                swap(arr, i, arr[i]-1)
        else:
            i += 1
    return i+1