题解 | #缺失的第一个正整数#

缺失的第一个正整数

https://www.nowcoder.com/practice/50ec6a5b0e4e45348544348278cdcee5

2022.0808算法第19题缺失的第一个正整数
哈希表也能解决这个问题,思路也很简单。
缺失的第一个正整数肯定是1-n+1之间的数,n为数组内元素的个数
因此只需要将数组内的元素存入哈希表,然后判断1-n+1之间的最小的不在hash中的数。
不采用hash存储时,也可以通过数组本身存储元素的特征,数组本身具有下标和值两个属性。
首先将非正数赋值为n+1,
for(int i=0;i<nums.size();i++){
    if(nums[i]<=0)
        nums[i]=nums.size()+1;
}
然后此时数组里的值变成1-n+1之间,
将数组元素的值,对应的下标的值赋值为负
for(int i=0;i<nums.size();i++){
    if(abs(nums[i])<=nums.size()){
        nums[abs(nums[i])-1]=abs(nums[abs(nums[i])-1])*-1;
    }              
}
这样第一个正数对应的下标就是数组缺失的第一个正整数
for(int i=0;i<nums.size();i++)
    if(nums[i]>0)
        return i+1;




#算法题#
全部评论

相关推荐

06-14 19:09
门头沟学院 Java
darius_:给制造业搞的,什么物料管理生产管理,设备管理点检,最最关键的就是一堆报表看板。个人觉得没啥技术含量都是些基本的crud,但是业务很繁琐那种
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务