当前位置：首页 > news >正文

017缺失的第一个正数

news 2026/5/6 8:30:10

缺失的第一个正数

题目链接：https://leetcode.cn/problems/first-missing-positive/?envType=study-plan-v2&envId=top-100-liked

我的解答：

无

分析：自己未能想出时间复杂度为O(n)且空间复杂度为O(1)的解法。

看了官方题解后的解答：

//方法一：哈希表 //时间复杂度：O(n) //空间复杂度：O(1) public int firstMissingPositive(int[] nums) { int ans=-1; int n=nums.length; //先将小于等于0的数变为n+1，以防判定答案时干扰 for(int i=0; i<n; i++){ if(nums[i]<=0){ nums[i]=n+1; } } //将数组模拟成哈希表，哈希函数为X-1，即数X应当放在X-1的位置，然后将此位置（假设为i）原有的数取负数作为标记 int num; for(int i=0; i<n; i++){ num=Math.abs(nums[i]); if(num<=n&&nums[num-1]>0){ nums[num-1]=-nums[num-1]; } } //遍历数组，若第一次出现i位置的数不是负数，则i+1就是数组没有出现的最小正整数 for(int i=0; i<n; i++){ if(nums[i]>0){ ans=i+1; break; } } return ans==-1 ? n+1 : ans; } //方法二：置换 //时间复杂度：O(n) //空间复杂度：O(1) public int firstMissingPositive(int[] nums) { int n=nums.length; for(int i=0; i<n; i++){ //判断当前位置的数是否在[1,n]范围内 并且 当前位置的数与需要被换到的位置的数不相等 while(nums[i]>=1 && nums[i]<=n && nums[nums[i]-1]!=nums[i]){ swap(nums,i,nums[i]-1); } } for(int i=0; i<n; i++){ if(nums[i]!=i+1){ return i+1; } } return n+1; } public void swap(int[] nums, int x, int y){ int temp=nums[x]; nums[x]=nums[y]; nums[y]=temp; }

分析：

1、题目的整体分析：对于一个长度为n的数组，数组缺失的正整数要么是[1,n]范围内的数，要么是n+1。按照常规思路，我们会考虑用哈希表存储数组的所有数，然后从1往后遍历，遍历到的第一个不属于哈希表中的数就是答案。但是题目要求只使用常数级别的额外空间，所以我们思考利用原有的数组nums，将其模拟为哈希表，从而求得答案。

2、方法一的思路是利用数据的正负性来标记这个数书否存在于数组中。首先我们将所有小于等于0的数赋值为n+1（不影响寻找答案），我们只要将大小在[1,n]范围内的数通过哈希函数X-1（X为数据的值）计算得到的位置处的数取为负数，最后遍历数组，遍历到的第一个数值非负的下标加一即为答案。

3、方法二的思路是将所有范围为[1,n]的元素按照方法二计算下标，并通过置换将其归位，最后某些位置的元素是不在[1,n]范围内且无法归位的，所以我们最后只需要遍历数组，找到第一个数值不等于下标加一的位置，这个位置加一即为答案。