41. 缺失的第一个正数 golang

最新推荐文章于 2021-12-10 09:36:27 发布

hodgeKou

最新推荐文章于 2021-12-10 09:36:27 发布

阅读量342

点赞数

分类专栏： LeetCode

本文链接：https://blog.csdn.net/csdn_kou/article/details/105334797

版权

LeetCode 专栏收录该内容

152 篇文章

订阅专栏

这是一篇关于使用Golang解决寻找未排序数组中缺失的第一个正整数问题的博客。通过示例输入和输出解释了算法逻辑，并强调了双百解法，即利用切片自身作为哈希表的优化思想。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

41. 缺失的第一个正数

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

示例 1:

输入: [1,2,0]
输出: 3
示例 2:

输入: [3,4,-1,1]
输出: 2
示例 3:

输入: [7,8,9,11,12]
输出: 1

Code

双百解法！这个题据说今日头条出过，注意最优解是让切片自己成为hash。记住这种思想很重要

func firstMissingPositive(nums []int) int {
	// 如果只有1就返回2
	if len(nums) == 1 {
		if nums[0] == 1 {
			return 2
		} else {
			return 1
		}
	}

	// 如果没有1返回1成功
	var flag_one int
	for _, v := range nums {
		if v == 1 {
			flag_one = 1
		}
	}
	if flag_one == 0{
		return 1
	}

	// 把所有的负数和大于n的数字置1
	for k, v := range nums {
		if v <= 0{
			nums[k] = 1
		}
		if v > len(nums) {
			nums[k] = 1
		}
	}

	// 把所有的出现数字中对应的value值乘以-1，代表这个数字出现了
	for _, v := range nums {
		if int(math.Abs(float64(v))) == len(nums) {
			nums[0] = int(math.Abs(float64(v)))
		} else if nums[int(math.Abs(float64(v)))] > 0 {
			nums[int(math.Abs(float64(v)))] *= -1
			if nums[0] < int(math.Abs(float64(v))) {
				nums[0] = int(math.Abs(float64(v)))
			}
		}
	}

	// 返回结果
	for i:=1; i<len(nums); i++ {
		if nums[i] > 0 {
			return i
		}
	}
	return nums[0] + 1
}


作者：HodgeKou
链接：https://leetcode-cn.com/problems/first-missing-positive/solution/go-shuang-bai-jie-fa-o1-on-by-hodgekou/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。