没网站能不能cpc广告点击赚钱做,可以自己做头像的网站,企业网站开发制作,保卫处网站建设文章目录 #x1f680;前言#x1f680;LeetCode#xff1a;41. 缺失的第一个正整数#x1f680;思路#x1f680;整个代码思路串一下#x1f680;Code #x1f680;前言
铁子们好啊#xff01;阿辉来讲道题#xff0c;这道题据说是23年字节3面真题#xff0c;LeetC… 文章目录 前言LeetCode41. 缺失的第一个正整数思路整个代码思路串一下Code 前言
铁子们好啊阿辉来讲道题这道题据说是23年字节3面真题LeetCode上面hard难度而且是很多难题的基础模板今天阿辉就带你拿下它
LeetCode41. 缺失的第一个正整数
链接缺失的第一个正数 给你一个未排序的整数数组 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的数字排好即可x1即为所求而排好这部分数我们仅需遍历一遍数组即可铁子们是不是要问为何如此因为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当前位置的数字为left1时left当left当前位置的数字处于left1到right之间且它本该在的位置也空出来的时候时left位置的数与这个数本该在的位置交换也就是num[left]与num[num[left]-1]的数交换当上面两种情况都不成立时left当前位置的数就是垃圾数与r-1位置的数交换并且--r垃圾区扩充
Code
class Solution {
public:int firstMissingPositive(vectorint nums) {int left 0;//左边界int right nums.size();//右边界while (left right) {//当left来到right时跳出循环if (nums[left] left 1) {//当left当前位置的数字为left1时leftleft;}//垃圾区else if (nums[left] left || nums[left] right || nums[left] nums[nums[left] - 1]) {swap(nums[left], nums[--right]);}//当left当前位置的数字处于left1到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)
