lintcode-189-丢失的第一个正整数

189-丢失的第一个正整数

给出一个无序的正数数组，找出其中没有出现的最小正整数。

样例

如果给出 [1,2,0], return 3
如果给出 [3,4,-1,1], return 2

挑战

只允许时间复杂度O(n)的算法，并且只能使用常数级别的空间。

标签

数组

思路

利用原有数组的空间，将素组元素位置重置，即 A[i+1] 应放在第 i 位（1 <= i <= n），如 1 放在 A[0]， 2 放在 A[1]，如此一来，再次遍历数组，若 A[i] != i + 1，即找到没有出现的最小正整数

code

class Solution {
public:
    /**    
     * @param A: a vector of integers
     * @return: an integer
     */
    int firstMissingPositive(vector<int> A) {
        // write your code here
        int size = A.size();
        if (size <= 0) {
            return 1;
        }
        for (int i = 0; i < size; ) {
            if (A[i] == i + 1) {
                i++;
            }
            if (A[i] >= 1 && A[i] <= size && A[i] != A[A[i] - 1]) {
                swap(A[i], A[A[i] - 1]);
            }
            else {
                i++;
            }
        }
        for (int i = 0; i < size; i++) {
            if (A[i] != i + 1) {
                return i + 1;
            }
        }
        return size + 1;
    }
};