文章目录

• 🚀前言
• 🚀LeetCode：41. 缺失的第一个正整数
• 🚀思路
• 🚀整个代码思路串一下
• 🚀Code

  🚀前言

  铁子们好啊！阿辉来讲道题，这道题据说是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)

  很明显可以想到二分或者有限次的遍历数组

  1. 对于本题，这道题让我们找到数组中缺失的第一个正整数，我们很容易想到排序然后便利数组，看看数组里面最先缺了谁，这道题就解决了，但是很遗憾时间复杂度限制在了O(n)空间复杂度O(1)不能用排序
  2. 不过上述的思考并非毫无意义，对于本题并非不能排序，因为我们要找的是缺失的第一个正整数，只要我们能够做到将数组中从1~x的数字排好即可，x+1即为所求，而排好这部分数我们仅需遍历一遍数组即可
  3. 铁子们是不是要问为何如此，因为1~x这些数字本身就决定了他们的位置，1本身就是他自己的索引，比如：1填在数组中0位置，2填在1位置，数字n填在n-1位置
  4. 对于一个长度为n的数组num，不一定整个数组都是1~n的数字，对于负数就属于垃圾，大于n的数也是垃圾，重复的数也是垃圾，为什么这么说，因为我们的目的是排1~x不间断连续的数字，其他的都没用，1~x排好了，这题也就拿下了
  5. 到这里兄弟们还觉得有难度吗？这不就是快拍的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& 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)

    

     
     深圳网站设计培训  怎么建造网站  制作网站一年多少钱  上海网站建设方案推广  网络策划专业  冷门行业创业有何优势