41. First Missing Positive

A[0] = 1;
A[1] = 2;
A[2] = 3;
A[i] = i+1;

if(A[i] != i+1)//puts A[i] into right place A[A[i]-1]

• why A[i]-1 ? 3 ->A[2=3-1] 4->A[3=4-1]

把1放在数组第一个位置A[0]，2放在第二个位置A[1]，即需要把A[i]放在A[A[i] - 1]上，那么我们遍历整个数组，如果A[i] != i + 1, 而A[i]为整数且不大于n，另外A[i]不等于A[A[i] - 1]的话，我们将两者位置调换，如果不满足上述条件直接跳过，最后我们再遍历一遍数组，如果对应位置上的数不正确则返回正确的数，代码如下：

 

void swap(int* nums, int j, int k) {
    int tmp = nums[k];
    nums[k] = nums[j];
    nums[j] = tmp;
}

int firstMissingPositive(int* nums, int numsSize) {
    int i = 0;
    int p = numsSize;

    while (i < p) {
        if (nums[i] == i+1)  ++i; // already in the right place,
        else if (nums[i] <= 0 || nums[i] > p || nums[i] == nums[nums[i]-1]) {
            swap(nums, i, --p); // out of range or duplicate, put it at the end
        } else {
            swap(nums, i, nums[i]-1); // within range; put it in the right place.
        }
    }

    return p + 1;
}