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.
思路：桶排序(bucket sort)，每当nums[i]!=i+1的时候，将nums[i]与nums[nums[i]-1]交换，直到无法交换为止，终止条件是nums[i]==nums[nums[i]-1]。
class Solution { public: int firstMissingPositive(vector<int>& nums) { int n=nums.size(); bucket_sort(nums,n); for(int i=0;i<n;i++){ if(nums[i]!=i+1) return i+1; } return n+1; } void bucket_sort(vector<int>&nums,int n){ for(int i=0;i<n;i++){ while(nums[i]!=i+1){ if(nums[i]<1||nums[i]>n||nums[i]==nums[nums[i]-1]) break; swap(nums[i],nums[nums[i]-1]); } } } };