1.思路

未排序的整数数组nums，需要找到缺失的第一个正整数，可以将数组中的内容添加到set中（主要考虑到set查询的速度优势），同时记录数组中的最大正整数n，之后从1到n遍历整数，对比遍历到的整数是否已经在set中。

具体思路是：

  1. 定义一个哈希表（set）；

  2. 将数组中的值存储到set中，其中n为数组中最大的数；

  3. 从自然数1开始到n，到map中找，如果对应的自然数没有找到，直接返回；

  4. [1:n]都在map中，则返回 n + 1。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
    def minNumberDisappeared(self, nums: List[int]) -> int:
        # write code here
        # 1.定义一个哈希表（set）
        hash_table = set()
        n = 1  # 数组中最大的数
        # 2. 将数组中的值存储到set中，数组中的最大值为n
        for e in nums:
            hash_table.add(e)
            if e > n:
                n = e
        # 3. 从自然数1开始到n，到set中找，如果对应的自然数没有找到，直接返回
        for i in range(1, n + 1):
            if i not in hash_table:
                return i
        # 4. 1~n都在set中，则返回n + 1
        return n + 1

2.2 Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int minNumberDisappeared (int[] nums) {
        // write code here
        //1.定义一个哈希表（set）
        Set<Integer> hashTable = new HashSet<>();
        int n = 1; //数组中最大的数
        //2.将数组中的值存储到set中，数组中的最大值为n
        for (int i = 0; i < nums.length; i++) {
            hashTable.add(nums[i]);
            if (nums[i] > n) {
                n = nums[i];
            }
        }
        //3.从自然数1开始到n，到set中找，如果对应的自然数没有找到，直接返回
        for (int i = 1; i <= n; i++) {
            if (!hashTable.contains(i)) {
                return i;
            }
        }
        //4. 1~n都在set中，则返回 n + 1
        return n + 1;
    }
}

2.3 Go代码


package main



/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型
 */
func minNumberDisappeared(nums []int) int {
	// write code here
	//1.定义一个哈希表（set，用map实现set的功能）
	hashTable := make(map[int]struct{})
	n := 1
	//2.将数组中的值存储到set中。key为：数组中的值，value：可以是任意值（没有实际意义），数组中的最大值为n
	for _, v := range nums {
		hashTable[v] = struct{}{}
		if v > n {
			n = v
		}
	}
	//3.从自然数1开始到n，到set中找，如果对应的自然数没有找到，直接返回
	for i := 1; i <= n; i++ {
		if _, ok := hashTable[i]; !ok {
			return i
		}
	}
	//4. 1~n都在set中，则返回 n + 1
	return n + 1
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构