力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
我们可以直接将数组中的数放到哈希表中,然后遍历[1,n],n为数组的大小,当遍历到某个数没有出现过的时候,就返回,若遍历完毕也没有,则返回n+1。
1、将负数转换为n+1
2、将在[1,n]的数转化为负数并且赋值到该数组对应数-1的下标位置
注意:切记切记我们在进行第二步的时候需要注意的是,遍历的这个位置
很可能之前已经被标记了,也就是已经被赋值为负数了,因此我们需要检测的是
它的绝对值是否符合条件,然后再使用该值进行进行进一步的赋值给对应绝对值数-1
的下标位置
3、返回数组中第一个不为负数的数+1
- class Solution
- {
- public:
- int firstMissingPositive(vector<int>& nums)
- {
- unordered_map<int,int> hash;
- for(auto&e:nums) hash[e]++;
- for(int i=1;i<=nums.size();i++)
- {
- if(hash[i]==0) return i;
- }
- return nums.size()+1;
- }
- };
- class Solution
- {
- public:
- int firstMissingPositive(vector<int>& nums)
- {
- int n=nums.size();
- // 1、将负数转换为n+1
- // 2、将在[1,n]的数转化为负数并且赋值到该数组对应数-1的下标位置
- // 注意:切记切记我们在进行第二步的时候需要注意的是,遍历的这个位置
- // 很可能之前已经被标记了,也就是已经被赋值为负数了,因此我们需要检测的是
- // 它的绝对值是否符合条件,然后再使用该值进行进行进一步的赋值给对应绝对值数-1
- // 的下标位置
- // 3、返回数组中第一个不为负数的数+1
- for(int&in:nums)
- {
- if(in<=0) in=n+1;
- }
-
- for(int i=0;i
- {
- int num=abs(nums[i]);
- if(num<=n)
- {
- int k=num-1;
- nums[k]=-abs(nums[k]);
- }
- }
-
- for(int i=0;i
- {
- if(nums[i]>0) return i+1;
- }
- return n+1;
- }
- };
-
相关阅读:
Java面试总结如何处理项目的高并发、大数据
【黄啊码】七夕来了,用JQuery给你女票表白吧
3-2主机发现-三层发现
【计算机网络系列】数据链路层④:扩展的以太网及其高速以太网
FlutterUnit 周边 | 收录排序算法可视化
A1048 Find Coins(测试点1)
脱口秀演员入职华为?破案了:人家还是博士后研究员
聊聊秒杀系统的设计(一)
行测-图形推理-3-对称图形类
C#多线程之线程基础篇
-
原文地址:https://blog.csdn.net/m0_57249790/article/details/132847206