41 First Missing Positive——leetcode

 

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

 

这个是"置换"思想，往深的说，这个与数学中的置换群有关。在TAOCP的排序章节中，开篇说的就是置换，而且有个题目：即，在O(N)时间，O(1)空间对数列{1,2,3,4,5,6,7,...}任意序列。进行原地排序。

先说排序：显然目标是A[i]=i+1

序列{2,1,4,3}，那么其置换(1,2)(3,4)，即1与2换位，3与4换位，置换个数=2

序列{4,1,2,3,1}，那么其置换为(2,3,4,1},置换个数=1。长度=4.即，用2代替1，3代替2,4代替3,1代替4；对比下：

4,1,2,3

2,3,4,1

将第一行位置K，用第二列第K位置的元素i替代，就可以变成有序的。

 

序列{1,2,3,4}那么其置换为(1),(2),(3),(4)，置换个数=4，如果置换个数=n，表明已经排序了。

因此，如果要排序，只要一次对其置换，进行处理

算法排序过程。注意序号是从0开始，而不是从1.

给定i，对某个置换排序：

如果A[i]的置换不为自己（即A[i]!=i+1)，那么将A[i]-1所在的元素用A[i]替代，将被替代的元素设置成A[i],重复上述。

否则，（该置换已经排序）。

排序过程基本如此。

——————————————————————————————————————————————

本题，可以看成是，去掉所有非0和负数，以及大于n的数。对所有1,2,3..n进行原地排序。

显然，排序完成后，应该有A[i]=i+1，如果某个A[i]!=i+1,说明缺失该元素。

算法复杂度分析：

《1》1所在的for循环执行N次

《2》2看起来像是N*N，其实不是，2循环内部的执行次数为置换的长度，一旦完成。会修改其他元素位置。因此进入while循环的次数恰好为置换的个数，而while循环体总内共执行的次数有恰好为该置换的长度。

《3》最后一个for循环，似乎可以修改为二分查找，实际查找的是第一个满足A[i]!=i+1的元素

 

 

    int firstMissingPositive(int A[], int n) { 
        for(int i=0;i<n;i++)//<1>对每个i，检查其置换
        {
            if(A[i]>n || A[i]<=0 || A[i]==i+1)
            {
                continue;
            }
            int j= A[i]-1;
            int last=A[i];
            int old=j;
            while(A[j]!=j+1){//<2>对A[i]-1位置的进行置换（排序过程）
                old = A[j];
                A[j] = last;
                j=old-1;
                last = old;
            }
        }
        for(int i=0;i<n;i++){
            if(A[i]!=i+1){
                return i+1;
            }
        }
        return n+1;
    }