(leetcode学习)41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
  请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
  
  示例 1：

1. <strong>输入：</strong>nums = [1,2,0]
2. <strong>输出：</strong>3
3. <strong>解释：</strong>范围 [1,2] 中的数字都在数组中。

复制代码

示例 2：

1. <strong>输入：</strong>nums = [3,4,-1,1]
2. <strong>输出：</strong>2
3. <strong>解释：</strong>1 在数组中，但 2 没有。

复制代码

示例 3：

1. <strong>输入：</strong>nums = [7,8,9,11,12]
2. <strong>输出：</strong>1
3. <strong>解释：</strong>最小的正数 1 没有出现。

复制代码

  提示：
  

• 1 <= nums.length <= 105
  
• -231 <= nums <= 231 - 1
  

  不管怎么说还是按照要求实现了，不看官方解法想不到
又学到一种方法，用正负数模拟哈希表

1. class Solution {
2. public:
3.     int firstMissingPositive(vector<int>& nums) {
4.         int res, n = nums.size();
5.         for(int i=0; i<n; i++){
6.             if(nums[i] <= 0) nums[i] = n + 1;
7.         }
8.         for(int i=0; i<n; i++){
9.             int cur = abs(nums[i]);
10.             if( cur <= n ){
11.                 nums[cur - 1] = -abs( nums[cur - 1] );
12.             }
13.         }
14.         for(res=0; res<n; res++){
15.             if(nums[res] > 0 ){
16.                 break;
17.             }
18.         }
19.         return res + 1;
20.     }
21. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。