41.first missing positive

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

Input: [1,2,0]
Output: 3

The idea is that we need to sort the array. We judge whether a number is missing or not by its index.

If value != index+1, then the missing number is index+1.

We first put all replaced numbers to their right index by swapping. For example, nums[i] is replaced, because the number in its right place is not equal to nums[i]. The right place should be nums[i]-1. So we need to exchange nums[nums[i]-1] with nums[i].

We can’t judge the replaced number by comparing nums[i] with i+1. Because when both nums[0] and nums[1] are 1, then nums[i] != 2 and swap(nums[1], nums[nums[1]-1]) won’t change the array.

1
2
3
4
5
6
7
8
9
10
11

int firstMissingPositive(vector<int>& nums) {
    int size = (int)nums.size();
    for(int i = 0; i < size; i++)
        while(nums[i] > 0 && nums[i] < size && nums[nums[i]-1] != nums[i])
            swap(nums[i], nums[nums[i]-1]);
    int k = 0;
    for(; k < size; k++)
        if(nums[k] != k+1)
            break;
    return k+1;
}