41. First Missing Positive

题意：

给一组无序数组，返回没有出现的最小正数，要求时间复杂度O（n），时间复杂度O(1)。

思路：

使每个数（如nums[i]）处在第nums[i]个位置（即与nums[nums[i]-1]交换）。然后再进行遍历，返回不符合的位置。

代码：

int firstMissingPositive(vector<int>& nums) {
	int sz = nums.size();
	for (int i = 0; i < nums.size(); ++i) {
		while (nums[i] > 0 && nums[i] < sz&&nums[nums[i] - 1] != nums[i])//while使得每次涉及的nums[i]都到第nums[i]个位置
			swap(nums[i], nums[nums[i] - 1]);
	}

	for (int i = 0; i < sz; ++i) {
		if (nums[i] != i + 1)
			return i + 1;
	}
	return sz;
}