Leetcode 41: first missing positive

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.

题意是： 给定一个长度为n的array，在这个array里面找到第一个miss 了的正数。

刚看到这个题目，想用之前1-n missing number的解法解，即sum之差，但是这个题目中混有非正数，不能简单的加减， 正确的方法是将里面所有的正数放在正确的位置，比如： 1-0， 2-1， 3-2,4-3.......所有正数与其对应的位置关系是num[i]-num[i]-1，看num[i]和num[num[i]-1]是否相同，如果不同，则swap这两个数， 这样就把num[i]放到了正确的位置，再看swap之后当前的i的位置是否正确。 将各个正数位置摆放正确之后，在扫描一遍array，看哪个位置缺数，如果不缺，返回n+1.

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        //sanity check
        if (nums.size() == 0) return 1;
        //sort the positive numbers: 每个正数应该在自己的位置上
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0 && nums[i] < nums.size()) {
                if (nums[nums[i] - 1] != nums[i]) {
                    swap(nums[i], nums[nums[i]-1]);
                    i--;
                }
            }
        }
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != i+1) {
                return  i+1;
            }
        }
        return nums.size()+1;
    
       
    }
};