题解 | #缺失的第一个正整数#

题目主要信息:

• 题目给定一个无序整型数组，没有重复元素，可能有负数或零，需要找出其中没有出现的最小正整数

举一反三：

学习完本题的思路你可以解决如下题目：

BM51. 数组中出现次数超过一半的数字

BM52. 数组中只出现一次的两个数字

方法一：哈希表（推荐使用）

知识点：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在$O(1)O(1)$时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

$nn$个长度的数组，没有重复，则如果数组填满了$1\mathrm{～}n1～n$，那么缺失$n+1n+1$，如果数组填不满$1\mathrm{～}n1～n$，那么缺失的就是$1\mathrm{～}n1～n$中的数字。对于这种快速查询某个元素是否出现过的问题，还是可以使用哈希表快速判断某个数字是否出现过。

具体做法：

• step 1：构建一个哈希表，用于记录数组中出现的数字。
• step 2：从1开始，遍历到n，查询哈希表中是否有这个数字，如果没有，说明它就是数组缺失的第一个正整数，即找到。
• step 3：如果遍历到最后都在哈希表中出现过了，那缺失的就是n+1.

Java实现代码：

import java.util.*;
public class Solution {
    public int minNumberDisappeared (int[] nums) {
        int n = nums.length;
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); 
        //哈希表记录数组中出现的每个数字
        for(int i = 0; i < n; i++) 
            mp.put(nums[i], 1);
        int res = 1;
        //从1开始找到哈希表中第一个没有出现的正整数
        while(mp.containsKey(res)) 
            res++;
        return res;
    }
}

C++实现代码：

class Solution {
public:
    int minNumberDisappeared(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> mp;
        //哈希表记录数组中出现的每个数字
        for(int i = 0; i < n; i++) 
            mp[nums[i]]++;
        int res = 1;
        //从1开始找到哈希表中第一个没有出现的正整数
        while(mp.find(res) != mp.end()) 
            res++;
        return res;
    }
};

Python实现代码：

class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        n = len(nums)
        mp = dict()
        #哈希表记录数组中出现的每个数字
        for i in range(n): 
            if nums[i] in mp:
                mp[nums[i]] += 1
            else:
                mp[nums[i]] = 1
        res = 1
        #从1开始找到哈希表中第一个没有出现的正整数
        while res in mp: 
            res += 1
        return res

复杂度分析：

• 时间复杂度：$O(n)O(n)$，第一次遍历数组，为$O(n)O(n)$，第二次最坏从1遍历到$nn$，为$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$，哈希表记录$nn$个不重复的元素，长度为$nn$

方法二：原地哈希（扩展思路）

思路：

前面提到了数组要么缺失$1\mathrm{～}n1～n$中的某个数字，要么缺失$n+1n+1$，而数组正好有下标$0\mathrm{～}n-10\; ～\; n-1$可以对应数字$1\mathrm{～}n1～n$，因此只要数字$1\mathrm{～}n1～n$中某个数字出现，我们就可以将对应下标的值做一个标记，最后没有被标记的下标就是缺失的值。

具体做法：

• step 1：我们可以先遍历数组将所有的负数都修改成n+1。
• step 2：然后再遍历数组，每当遇到一个元素绝对值不超过n时，则表示这个元素是1～n中出现的元素，我们可以将这个数值对应的下标里的元素改成负数，相当于每个出现过的正整数，我们把与它值相等的下标都指向一个负数，这就是类似哈希表的实现原理的操作。
• step 3：最后遍历数组的时候碰到的第一个非负数，它的下标就是没有出现的第一个正整数，因为它在之前的过程中没有被修改，说明它这个下标对应的正整数没有出现过。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public int minNumberDisappeared (int[] nums) {
        int n = nums.length;
        //遍历数组
        for(int i = 0; i < n; i++) 
            //负数全部记为n+1
            if(nums[i] <= 0) 
                nums[i] = n + 1;
        for(int i = 0; i < n; i++)
            //对于1-n中的数字
            if(Math.abs(nums[i]) <= n) 
                //这个数字的下标标记为负数
                nums[Math.abs(nums[i]) - 1] = -1 * Math.abs(nums[Math.abs(nums[i]) - 1]); 
        for(int i = 0; i < n; i++)
            //找到第一个元素不为负数的下标
            if(nums[i] > 0)
                return i + 1;
        return n + 1;
    }
}

C++实现代码：

class Solution {
public:
    int minNumberDisappeared(vector<int>& nums) {
        int n = nums.size();
        //遍历数组
        for(int i = 0; i < n; i++) 
            //负数全部记为n+1
            if(nums[i] <= 0) 
                nums[i] = n + 1;
        for(int i = 0; i < n; i++)
            //对于1-n中的数字
            if(abs(nums[i]) <= n) 
                //这个数字的下标标记为负数
                nums[abs(nums[i]) - 1] = -1 * abs(nums[abs(nums[i]) - 1]); 
        for(int i = 0; i < n; i++)
            //找到第一个元素不为负数的下标
            if(nums[i] > 0)
                return i + 1;
        return n + 1;
    }
};

Python实现代码：

class Solution:
    def minNumberDisappeared(self , nums: List[int]) -> int:
        n = len(nums)
        #遍历数组
        for i in range(n): 
            #数全部记为n+1
            if nums[i] <= 0: 
                nums[i] = n + 1
        for i in range(n):
            #对于1-n中的数字
            if abs(nums[i]) <= n: 
                #这个数字的下标标记为负数
                nums[abs(nums[i]) - 1] = -1 * abs(nums[abs(nums[i]) - 1]) 
        for i in range(n):
            #找到第一个元素不为负数的下标
            if nums[i] > 0: 
                return i + 1
        return n + 1

复杂度分析：

• 时间复杂度：$O(n)O(n)$，多次遍历数组，都是单层循环
• 空间复杂度：$O(1)O(1)$，原地哈希，以索引为指向，没有额外空间