哪些平台可以推广产品_保定百度推广排名_网络优化器_seo网站优化培训公司

题目描述：

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

输入输出样例：

示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：
1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

题解：

解题思路：

思路一（哈希表：不满足空间O(n)的条件）：
1、题目要求其中没有出现的最小的正整数。
例：
①如果nums=[1,2,3]，ans=4
②如果nums=[-1,2,3]，ans=1

2、具体思路如下：
① 我们会发现ans的范围会是 [1,nums.size()+1]，所以我们可以创建ans大小的hashmap。
② key赋值为[1,nums.size()+1]，value=0。
③ 如果nums中有对应的key则value+1。
④ 最后通过判断hashmap中第一个出现0的位置确定最小的正整数，如果都不为0，则返回nums.size()+1。

3、复杂度分析：
① 时间复杂度：O(N),N代表nums.size()，遍历三次N大小的容器O(N) 。
② 空间复杂度：O(N),创建一个nums.size()大小的哈希表O(N)。

思路二（将原数组视为哈希表）：
1、方法一的思想是如果出现数字i，那么我就将i记录一下，且考虑ans的范围会是 [1,nums.size()+1]，那我们可以采用同样的思想，只使用nums原数组，其实就是将1~nums.size()元素移动到其最终位置，通过判断元素大小和位置的对应关系来定位缺失的第一个正数。
例子：nums=[1,3,4,5]
① nums=[1,3,4,5] ,1在最终位置
② nums=[1,4,3,5] ,3不在最终位置，3与4交换
③ nums=[1,5,3,4] ,4不在最终位置，4与5交换
④ nums=[1,5,3,4] ,5超出范围
⑤ nums=[1,5,3,4] ,3在最终位置
⑥ nums=[1,5,3,4] ,4在最终位置

2、具体思路如下：
① 假设nums=[3,4,-1,1],第一个数字nums[0]=3，先判断nums[0]是否为1（是则转到第二个元素），我们可以将3放在数组中第3个位置也就是nums[3-1]。
② 为了防止数据的丢失这里我们将3和-1进行交换nums=[-1,4,3,1]
③ 此时我们还需对nums[0]进行判断，直到nums[0]的范围超出[1,nums.size()]或者交换的元素是相同元素【2，2】或者num[i]=i+1时跳转到下一个元素。
④ 依次重复上述过程直到最后一个元素
⑤ 此时我们可以通过nums[i]==i+1来判断，是否缺失正整数。如果都满足nums[i]==i+1则返回nums.size()+1。

3、复杂度分析
① 时间复杂度：O(N),N代表nums.size()，遍历一遍容器，且内层while循环一次，将有一个整数n，放置在下标n-1处，所以为O(N)。
② 空间复杂度：O(1),只对原nums容器进行操作，所以为O(1)。

代码实现（思路一（哈希表））：

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;int firstMissingPositive1(vector<int>& nums) {unordered_map<int,int> mp;for(int i=1;i<=nums.size();i++){mp[i]=0; }//将nums映射到mp中的对应位置 for(const auto &num:nums){if(mp.count(num)){mp[num]++;}}//查找第一个为0的位置为最小的正整数 for(int i=1;i<=mp.size();i++){if(mp[i]==0){return i;}}return nums.size()+1;
}int main(){vector<int> nums={1,2,0};cout<<firstMissingPositive1(nums);return 0;
}

代码实现（思路二（将原数组视为哈希表））：

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;int firstMissingPositive2(vector<int>& nums) {//将整数i存放在 i-1的位置，注意重复元素的判断nums[i]==nums[nums[i]-1] for(int i=0;i<nums.size();i++){//整数不在最终位置进入循环 while(nums[i]!=i+1){//当交换过来的元素超出[1,nums.size()]或者已经在最终位置如[1,1],跳转到下一个位置 if(nums[i]<=0||nums[i]>nums.size()||nums[i]==nums[nums[i]-1])break;swap(nums[i],nums[nums[i]-1]);}
//		或者写成如下形式
//		while((nums[i]!=i+1)&&(nums[i]>0&&nums[i]<=nums.size())&&nums[i]!=nums[nums[i]-1]){
//			swap(nums[i],nums[nums[i]-1]);
//		}} //查找没有出现的最小的正整数for(int i=0;i<nums.size();i++){if(nums[i]!=i+1){return i+1;}	}return nums.size()+1;
}int main(){vector<int> nums={1,2,0};cout<<firstMissingPositive2(nums);return 0;
}

部分代码解读

unordered_map初始化设置默认值

//可以在创建 unordered_map 时指定其初始桶数
//unordered_map 本身没有默认值，但你可以通过访问不存在的键来设置默认值
unordered_map<int,int> mp(size);
for(int i=1;i<=nums.size();i++){mp[i]=0; 
}

LeetCode 热题 100_缺失的第一个正数（17_41)原题链接

欢迎大家和我沟通交流(✿◠‿◠)