循环不变式
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
