第一个缺失的整数

声明： 本总结仅为个人学习总结，以防止遗忘而作，不得转载和商用。
给定一个数组 A[0…N−1],找到从1开始,第一个不在数组中的正整数.
如 3,5,1,2,−3,7,14,8输出4

循环不变式:
思路：将找到的元素放到正确的位置上,如果最终发现某个元素一直没有找到,则该元素即为所求.
如果某命题初始为真，且每次更改后仍然保持该命题为真，则若干次更改后该命题仍然为真。
利用循环不变式设计算法
假定前 i−1 个数已经找到，并且依次存放在 A[1,2,…,i−1] 中，继续考察 A[i] ：

1. 若 A[i]＜i且A[i]≥1 ，则 A[i] 在 A[1,2,…,i−1] 中已经出现过，可以直接丢弃。
2. 若 A[i] 为负，则更应该丢弃它。
3. 若 A[i]＞i 且 A[i]≤N ，则 A[i] 应该置于后面的位置，即将 A[A[i]] 和 A[i] 交换。
4. 若 A[A[i]]＝A[i] ，则显然不必交换，直接丢弃 A[i] 即可。
5. 若 A[i]＞N，超出范围，则 A[i] 丢弃。
6. 若 A[i]＝i ，则 A[i] 位于正确的位置上，则 i 加1，循环不变式扩大，继续比较后面的元素。
   整理算法：
7. 若 A[i]＝i ，i 加1，继续比较后面的元素。
8. 若 A[i]＜i 或 A[i]＞N 或 A[A[i]]＝A[i] ，丢弃 A[i]
9. 若 A[i]＞i ，则将 A[A[i]]和A[i] 交换。
   思考：如何快速丢弃（删除） A[i] ？（重要的思想）
   如果按常规的思想删除数组里的元素，那么删除某个元素后，其后面的元素需要依次的向前移动，其时间复杂度至少 O(n) 。如果将 A[N] 赋值给 A[i] ，然后 N 减1，相当于把 A[N] 丢弃了，A[N] 就是互换之前的 A[i] 。则只需要 O(1) 的时间复杂度就删除了元素。
   这里需要如果注意丢弃了一个元素，则可表示的连续序列最长的长度会减1，因为数组中剩余的元素个数减少了1。

Java版本实现代码

public static int firstMissNumber(int[] a){
        int size = a.length;
        int A[] = new int[size+1];
        A[0] = 0;
        for(int i=0;i<a.length;i++){
            A[i+1] = a[i];
        }
        int i = 1;//数组下标均加1,从1开始计,在原始数组a上进行操作使得a[size] = {1,2,3,...,size}
        while (i<=size) {
            if (A[i] == i) {
                i++;//只有在A[i] == i时才前进一步,如果遇到缺少的,则始终得不到a[i]==i
            }else if (A[i] < i || A[i] > size || A[i] == A[A[i]]) {//丢弃A[i]
                //如果a[i]!=i，若
                //a[i]<i表示有重复;a[i]>size表示超出可表示有序数组;a[i] == a[a[i]]则下面的互换无意义
                //丢弃一个元素，则可表示的有序数组长度减1
                A[i] = A[size];
                size--;
            }else {//如果a[i]!=i且i<a[i]<=size，则进行互换，将a[i]换到数组中正确的位置上。
//              swap(a[i], a[a[i]]);
                int temp = A[i];
                A[i] = A[temp];
                A[temp] = temp;
            }
        }
        return i;
    }

测试代码：

        int a[] = { 3, 5, 1, 2, -3 , 6, 7 , 4, 8 };
        int m = firstMissNumber(a);
        System.out.println(m);

输出结果：9