LeetCode 41:First Missing Positive

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.

 //類似於桶排序，交換數組元素，使得數組中第i位存放數值(i+1);
 //最後遍歷數組，尋找第一個不符合此要求的元素，返回其下標。整個過程需要遍歷兩次數組，復雜度為O(n)。
 class Solution {
 public:
	 int firstMissingPositive(vector& nums) {
		 int n = nums.size();
		 for (int i = 0; i < n; ++i)
		 {
			 while (nums[i]>0 && nums[i] < n && nums[nums[i]-1] !=nums[i])
				 swap(nums[nums[i]-1], nums[i]);
		 }
		 for (int i= 0; i < n; ++i)
		 {
			 if (nums[i] != i + 1)
				 return i + 1;
		 }
		 return n + 1;
	 }
 };