【数据结构-哈希表 一】【原地哈希】：缺失的第一个正整数

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【原地哈希】，使用【数组】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。

明确目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

缺失的第一个正整数【HARD】

又是一道考验数组结构与哈希表结合的题

题干

直接粘题干和用例

解题思路

原题解地址由于题目要求我们「只能使用常数级别的空间」，而要找的数一定在 [1, N + 1] 左闭右闭（这里 N 是数组的长度）这个区间里。因此，我们可以就把原始的数组当做哈希表来使用。事实上，哈希表其实本身也是一个数组，我们要找的数就在 [1, N + 1] 里，最后 N + 1 这个元素我们不用找。因为在前面的 N 个元素都找不到的情况下，我们才返回 N + 1；

1. ** 按照桶排序思路进行预处理：保证 1 出现在 nums[0] 的位置上，2 出现在 nums[1] 的位置上，…，n 出现在 nums[n - 1] 的位置上。不在 [1, n] 范围内的数不用动**。例如样例中 [3,4,-1,1] 将会被预处理成 [1,-1,3,4]。
2. 遍历 nums，找到第一个不在应在位置上的 [1, n] 的数。如果没有找到，说明数据连续，答案为 n + 1。例如样例预处理后的数组 [1,-1,3,4] 中第一个 nums[i] != i + 1 的是数字 2（i = 1）。

这个思想就相当于我们自己编写哈希函数，这个哈希函数的规则特别简单，那就是数值为 i 的数映射到下标为 i - 1 的位置。

代码实现

给出代码实现基本档案

基本数据结构：数组
辅助数据结构：无
算法：迭代
技巧：双指针（逆序双指针）

其中数据结构、算法和技巧分别来自：

• 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
• 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
• 技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int minNumberDisappeared (int[] nums) {
        // 原地hash：元素位置+1=元素值(i+1=nums[i]=>i=nums[i]-1)，才满足各回各家，先将元素归位
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > 0 && nums[i] < nums.length && nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }

        // 遍历一遍数组，找到第一个不符合条件的返回
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i+1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }

    // 交换元素位置
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

原地哈希就相当于，让每个数字n都回到下标为n-1的家里，那些没有回到家里的就成了流浪汉，他们要么是根本就没有自己的家（数字小于等于0或者大于nums.size()），要么是自己的家被别人占领了（出现了重复）。这些流浪汉被临时安置在下标为i的空房子里，之所以有空房子是因为房子i的主人i+1失踪了（数字i+1缺失）。因此通过原地构建哈希让各个数字回家，我们就可以找到原始数组中重复的数字还有消失的数字。

• 为什么内部是while循环，我们的目标是把nums[i]在[1,N]范围内的数字归位，所以每个有家的流浪汉都要找到它的房子，i位置上的流浪汉找到了自己的房子nums[i]-1，但nums[i]-1房子被赶出来的流浪汉的房子却未必是i位置，它需要临时住在i并继续找自己的房子。所以直到nums[i]-1换回来的流浪汉正好对应i这个房子或这个流浪汉压根就没房子（非【1-N】范围的值），这次寻找才算结束
• 判断条件为什么有nums[i] > 0 && nums[i] < nums.length，对于[7,8,9,10]，这种数来说，因为不可能满足哈希映射条件，交换操作还会导致数组越界，所以没必要也不能进行移动；流浪汉压根没房子
• 判断条件为什么是 nums[i] != nums[nums[i] - 1]。因为对于[3,4,3,1]，这种数来说，i!=nums[i]-1虽然满足条件，但是交换后因为还是[3,4,3,1]，所以会导致一直交换死循环，所以要采取更严苛的判断条件避免重复元素交换，也就是交换位置上的数不能相同！而且值得注意的是满足 nums[i] != nums[nums[i] - 1]其实就一定满足i!=nums[i]-1

复杂度分析

• 时间复杂度：O(N)。遍历了一遍数组，时间复杂度为O（N）
• 空间复杂度：O(1)。 需要建立长度为 m+n 的中间数组