当前位置: 首页> 房产> 政策 > 41 缺失的第一个整数

41 缺失的第一个整数

时间:2025/7/11 8:34:27来源:https://blog.csdn.net/midi666/article/details/140136149 浏览次数:0次
题目

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

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

实例

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

解析

这道题正常的写法是用哈希,但是这道题要求原地,那就使用一种原地哈希的思路.
首先遍历数组,要做的就是数组的每个位置中,存的是每个位置对应的数,不满足的就在对应的位置进行交换.

比如有[3,4,5,-1,1,255],nums[0] = 3 和nums[0]-1 = 2为下标的值(即nums[2] = 5)进行交换,遍历完成后就保证了:i+1位置存的就是nuns[i]的数,比如nums[0] = 1

func firstMissingPositive(nums []int) int {n := len(nums)for i := 0; i < n; i++ {for nums[i] > 0 && nums[i] < n && nums[i] != nums[nums[i]-1] {nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]}}for i := 0; i < n; i++ {// 如果当前元素不等于它的索引+1,那索引+1就是第一个缺失的正整数if nums[i] != i+1 {return i + 1}}// 没有的话,缺失的正整数就是数组长度+1return n + 1
}

这个解法还是很不好理解的,再多看看

关键字:41 缺失的第一个整数

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: