广东官方网站建设,郑州二七区,c语言网站,wordpress首页如何增加模块废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【原地哈希】#xff0c;使用【数组】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为…废话不多说喊一句号子鼓励自己程序员永不失业程序员走向架构本篇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 的是数字 2i 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元素值(i1nums[i]inums[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] ! i1) {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的主人i1失踪了数字i1缺失。因此通过原地构建哈希让各个数字回家我们就可以找到原始数组中重复的数字还有消失的数字。
为什么内部是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)。遍历了一遍数组时间复杂度为ON空间复杂度O(1)。 需要建立长度为 mn 的中间数组
