制作网站找哪个公司好,asp.net网站开发教程,百度下载app下载安装,延庆城市建设网站41 缺失的第一个正数
给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1#xff1a; 输入#xff1a;nums [1,2,0] 输出#xff1a;3 解释#xff1a;范围 [1…41 缺失的第一个正数
给你一个未排序的整数数组 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 n u m s . l e n g t h 1 0 5 1 nums.length 10^5 1nums.length105 − 2 31 n u m s [ i ] 2 31 − 1 -2^{31} nums[i] 2^{31} - 1 −231nums[i]231−1
思路
本题采用哈希表思想使用 mapint,int m 记录数组中正整数元素是否存在注意根据题意只需记录正整数元素即可同时需要记录数组最大值 maxN注意maxN初始化为0。 遍历1到maxN若m中存在该范围的所有数则输出maxN1否则输出不存在的数即可满足题意。
代码
class Solution {
public:int firstMissingPositive(vectorint nums) {mapint, int m;int maxN 0;for (int i 0; i nums.size(); i) {if (nums[i] 0) {m[nums[i]] 1;if (maxN nums[i]) {maxN nums[i];}}}int ans -1;for (int i 1; i maxN; i) {if (m[i] 0) {ans i;break;}}return ans -1 ? maxN 1 : ans;}
};
