缺失的第一个整数
大约 2 分钟
缺失的第一个整数
思路分析
题目限制:时间复杂度为 O(n)
并且只使用常数级别额外空间的解决方案。
题目限制时间复杂度是o(n)级别内找到缺失的第一个整数,意味着不能使用排序的方法;
核心是判断从1开始,哪一个数字没有出现在数组中,因此可以将数组中的元素放到set集合中,然后使用累加变量逐步累加,判断是否在set集合中出现,如果出现就累加1,直到不出现为止;
代码实现
java实现
public class FirstMissingPositive {
public static void main(String[] args) {
int []arr ={3,4,-1,1};
int i = firstMissingPositive(arr);
System.out.println(i);
}
/**
* 输入:nums = [1,2,0]
* 输出:3
* 解释:范围 [1,2] 中的数字都在数组中。
* @author yourname
* @date 20:00 2024/12/26
* @param nums
* @return int
**/
public static int firstMissingPositive(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
HashSet<Integer> sets = new HashSet<>();
for(int num:nums){
sets.add(num);
}
int addNum=1;
while (sets.contains(addNum)){
addNum++;
}
return addNum;
}
}
go实现
func firstMissingPositive(nums []int) int {
if nums == nil || len(nums) == 0 {
return 0
}
/*创建map当作set使用*/
mapTmp := make(map[int]bool)
/*遍历数组,返回index,val 如果不需要index,就是用_代替*/
for _, num := range nums {
mapTmp[num] = true
}
for addSum := 1; ; {
if _, ok := mapTmp[addSum]; ok {
addSum++
} else {
return addSum
}
}
return 0
}