缺失的第一个正数题目链接https://leetcode.cn/problems/first-missing-positive/?envTypestudy-plan-v2envIdtop-100-liked我的解答无分析自己未能想出时间复杂度为O(n)且空间复杂度为O(1)的解法。看了官方题解后的解答//方法一哈希表 //时间复杂度O(n) //空间复杂度O(1) public int firstMissingPositive(int[] nums) { int ans-1; int nnums.length; //先将小于等于0的数变为n1以防判定答案时干扰 for(int i0; in; i){ if(nums[i]0){ nums[i]n1; } } //将数组模拟成哈希表哈希函数为X-1即数X应当放在X-1的位置然后将此位置假设为i原有的数取负数作为标记 int num; for(int i0; in; i){ numMath.abs(nums[i]); if(numnnums[num-1]0){ nums[num-1]-nums[num-1]; } } //遍历数组若第一次出现i位置的数不是负数则i1就是数组没有出现的最小正整数 for(int i0; in; i){ if(nums[i]0){ ansi1; break; } } return ans-1 ? n1 : ans; } //方法二置换 //时间复杂度O(n) //空间复杂度O(1) public int firstMissingPositive(int[] nums) { int nnums.length; for(int i0; in; i){ //判断当前位置的数是否在[1,n]范围内 并且 当前位置的数与需要被换到的位置的数不相等 while(nums[i]1 nums[i]n nums[nums[i]-1]!nums[i]){ swap(nums,i,nums[i]-1); } } for(int i0; in; i){ if(nums[i]!i1){ return i1; } } return n1; } public void swap(int[] nums, int x, int y){ int tempnums[x]; nums[x]nums[y]; nums[y]temp; }分析​ 1、题目的整体分析对于一个长度为n的数组数组缺失的正整数要么是[1,n]范围内的数要么是n1。按照常规思路我们会考虑用哈希表存储数组的所有数然后从1往后遍历遍历到的第一个不属于哈希表中的数就是答案。但是题目要求只使用常数级别的额外空间所以我们思考利用原有的数组nums将其模拟为哈希表从而求得答案。​ 2、方法一的思路是利用数据的正负性来标记这个数书否存在于数组中。首先我们将所有小于等于0的数赋值为n1不影响寻找答案我们只要将大小在[1,n]范围内的数通过哈希函数X-1X为数据的值计算得到的位置处的数取为负数最后遍历数组遍历到的第一个数值非负的下标加一即为答案。​ 3、方法二的思路是将所有范围为[1,n]的元素按照方法二计算下标并通过置换将其归位最后某些位置的元素是不在[1,n]范围内且无法归位的所以我们最后只需要遍历数组找到第一个数值不等于下标加一的位置这个位置加一即为答案。总结本题主要是需要分析出缺失的本质想要不缺失那数组一定从1开始连续一直到n如果1到n都是连续没有缺失的那么答案就为n1否则答案一定在[1,n]范围内掌握这个性质之后我们可以利用原本的数组模拟哈希表或是标记或是归位最终遍历找出答案。