class Solution {

 public:

     int firstMissingPositive(vector<int>& nums) {

         //这是看了解答后的代码 满足题意 但速度没提高太多

         int size = nums.size();

         int *numsHash;

         int size_hash = size +;

         //创建一个哈希表 初始化为0

         numsHash = new int[size_hash]();

         //遍历nums 对于小于数组长度的元素在哈希表中打个标记

         //对于比数组长度大的数据可以忽略，因为第一个缺失的正数没这么大

         for (int i = ; i < size; ++i)

         {

             if (nums[i] >  && nums[i] < size_hash)

             {

                 numsHash[nums[i]] = ;

             }

         }

         //遍历哈希表 找出第一个没打标记的

         int *end_pos = numsHash + size_hash;

         for (int *p = numsHash + ; p != end_pos; ++p)

         {

             if (*p == )

             {

                 return p - numsHash;

             }

         }

         return size_hash;

     }

     int firstMissingPositiveNew(vector<int>& nums) {

         //这是我自己想的答案，不符合题目O(n)要求，但排名也挺高

         //排序  然后找出第一个大于0的数字

         //顺序查找下去，直到发现本元数比上一个元素大1就说明找到了

         sort(nums.begin(), nums.end());
　　　　　　 //从1开始找出第一个不在数组里面的正数  慢

         //for (int i = 1; i <= INT_MAX; ++i)

         //{

         //    if (!binary_search(nums.begin(), nums.end(), i))

         //    {

         //        return i;

         //    }

         //}

         auto it = upper_bound(nums.begin(), nums.end(), );

         if (it == nums.end() || *it != ) return ;

         for (++it; it != nums.end(); ++it)

         {

             if ((*it - *(it - )) > )

             {

                 return *(it - ) + ;

             }

         }

         return *(it - ) + ;

     }

 };