网站设计与网站制作手机网站模版 优帮云
废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【原地哈希】，使用【数组】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。
明确目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。
缺失的第一个正整数【MID】
又是一道考验数组结构与哈希表结合的题
题干
直接粘题干和用例
解题思路
原题解地址由于题目要求我们「只能使用常数级别的空间」，而要找的数一定在 [1, N + 1] 左闭右闭（这里 N 是数组的长度）这个区间里。因此，我们可以就把原始的数组当做哈希表来使用。事实上，哈希表其实本身也是一个数组，我们要找的数就在 [1, N + 1] 里，最后 N + 1 这个元素我们不用找。因为在前面的 N 个元素都找不到的情况下，我们才返回 N + 1；
- ** 按照桶排序思路进行预处理：保证 1 出现在 nums[0] 的位置上，2 出现在 nums[1] 的位置上，…，n 出现在 nums[n - 1] 的位置上。不在 [1, n] 范围内的数不用动**。例如样例中 [3,4,-1,1] 将会被预处理成 [1,-1,3,4]。
- 遍历 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;}
}
原地哈希就相当于，让每个数字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 的中间数组