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

样例

如果给出 [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
    
      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;    }};