🚀前言
铁子们好啊!阿辉来讲道题,这道题据说是23年字节3面真题,LeetCode上面hard
难度,而且是很多难题的基础模板,今天阿辉就带你拿下它!!!
🚀LeetCode:41. 缺失的第一个正整数
链接🔗:缺失的第一个正数
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1:
输入:nums = [1,2,0]
输出:3
示例 2:
输入:nums = [3,4,-1,1]
输出:2
示例 3:
输入:nums = [7,8,9,11,12]
输出:1
🚀思路
首先这道题要求时间复杂度在O(n),空间复杂度在O(1)
很明显可以想到二分或者有限次的遍历数组
- 对于本题,这道题让我们找到数组中缺失的第一个正整数,我们很容易想到排序然后便利数组,看看数组里面最先缺了谁,这道题就解决了,但是很遗憾时间复杂度限制在了O(n)空间复杂度O(1)不能用排序
- 不过上述的思考并非毫无意义,对于本题并非不能排序,因为我们要找的是缺失的第一个正整数,只要我们能够做到将数组中从
1~x
的数字排好即可,x+1
即为所求,而排好这部分数我们仅需遍历一遍数组即可 - 铁子们是不是要问为何如此,因为
1~x
这些数字本身就决定了他们的位置,1
本身就是他自己的索引,比如:1
填在数组中0
位置,2
填在1
位置,数字n
填在n-1
位置 - 对于一个长度为
n
的数组num
,不一定整个数组都是1~n
的数字,对于负数就属于垃圾,大于n
的数也是垃圾,重复的数也是垃圾,为什么这么说,因为我们的目的是排1~x
不间断连续的数字,其他的都没用,1~x
排好了,这题也就拿下了 - 到这里兄弟们还觉得有难度吗?这不就是快拍的
partition
划分过程吗?拿下!!!!
🚀整个代码思路串一下
首先,我们准备两个数组偏移量left = 0
和right = n
(n
代表数组的长度),left
的位置表示待排序的位置,right
首先是垃圾区的边界,其次right
还表示能够排完整个连续不间断正整数数列的长度,所以一开始,right
为n
- 当
left
当前位置的数字为left+1
时,++left
- 当
left
当前位置的数字处于left+1
到right
之间且它本该在的位置也空出来的时候时,left
位置的数与这个数本该在的位置交换,也就是num[left]
与num[num[left]-1]
的数交换 - 当上面两种情况都不成立时,
left
当前位置的数就是垃圾数,与r-1
位置的数交换,并且--r
垃圾区扩充
🚀Code
class Solution { public: int firstMissingPositive(vector<int>& nums) { int left = 0;//左边界 int right = nums.size();//右边界 while (left < right) {//当left来到right时跳出循环 if (nums[left] == left + 1) {//当left当前位置的数字为left+1时,++left ++left; } //垃圾区 else if (nums[left] <= left || nums[left] > right || nums[left] == nums[nums[left] - 1]) { swap(nums[left], nums[--right]); } //当`left`当前位置的数字处于`left+1`到`right`之间 //且它本该在的位置也空出来的时候时 else { swap(nums[left], nums[nums[left] - 1]); } } return left + 1;//要加1,因为1在0位置,n就在n-1位置 } };
复杂度
时间复杂度:
O ( n ) O(n)O(n)
空间复杂度:
: O ( 1 ) O(1)O(1)