0041. First Missing Positive

41. First Missing Positive #

题目 #

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:


Input: [1,2,0]  
Output: 3  

Example 2:


Input: [3,4,-1,1]  
Output: 2  

Example 3:


Input: [7,8,9,11,12]  
Output: 1  

Note:

Your algorithm should run in O(n) time and uses constant extra space.

题目大意 #

找到缺失的第一个正整数。

解题思路 #

为了减少时间复杂度,可以把 input 数组都装到 map 中,然后 i 循环从 1 开始,依次比对 map 中是否存在 i,只要不存在 i 就立即返回结果,即所求。

代码 #


package leetcode

func firstMissingPositive(nums []int) int {
	numMap := make(map[int]int, len(nums))
	for _, v := range nums {
		numMap[v] = v
	}
	for index := 1; index < len(nums)+1; index++ {
		if _, ok := numMap[index]; !ok {
			return index
		}
	}
	return len(nums) + 1
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者