Python中的最小缺失整数

第一个缺失的整数识别

对于一个给定的数组A[0…N-1]，需要确定从1开始的第一个未在数组中出现的正整数。例如，当数组元素为3,5,1,2,-3,7,14,8时，所求结果应为4。

循环不变式

核心思想在于将识别出的要素归置至其对应的位置，若在执行过程中发现某一要素始终未能被定位，则可判定该要素即为目标。
循环不变性原则指出，若某一命题在初始状态成立，并且在每次操作后依然维持其成立状态，则经过多次操作后该命题依旧成立。
为便于表述，以下算法说明将从数字1开始进行计数。

循环不变式在算法设计中的应用

假设前i-1个数值已经被确定，并按顺序存储于数组A[1,2,…,i-1]中，接下来对A[i]进行分析：
若A[i]的值小于i且不小于1，则说明该数值在A[1,2,…,i-1]中已存在，可直接忽略。
当A[i]为负数时，更应将其排除。
如果A[i]大于i且不超过N，则表明该数值应出现在后续的位置，此时需将A[A[i]]与A[i]进行互换操作。
若A[i]的值大于或等于N，由于缺失的数据必定小于N，因此该数值应被舍弃。
当A[i]等于i时，说明当前元素处于正确的位置上，此时将i增加1，并扩展循环不变式的范围，继续对后续元素进行判断。

分支合并策略与实现

算法描述整理：
当A[i]的值小于i或大于N时，应将其从数组