字节3面真题,LeetCode上hard难度,极具启发性题解

简介: 字节3面真题,LeetCode上hard难度,极具启发性题解

🚀前言

铁子们好啊!阿辉来讲道题,这道题据说是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 = 0right = n(n代表数组的长度),left的位置表示待排序的位置,right首先是垃圾区的边界,其次right还表示能够排完整个连续不间断正整数数列的长度,所以一开始,rightn

  • left当前位置的数字为left+1时,++left
  • left当前位置的数字处于left+1right之间且它本该在的位置也空出来的时候时,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)

相关文章
|
6月前
|
算法 Java C语言
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
38 1
|
6月前
|
算法 数据挖掘 Python
LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】
LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】
|
7月前
[leetcode~数位动态规划] 2719. 统计整数数目 hard
[leetcode~数位动态规划] 2719. 统计整数数目 hard
|
算法 程序员 容器
跨年巨作!字节技术官手码1938页LeetCode热门高解,GitHub已上榜
一直以来,刷力扣都是程序员学习算法路上最大的绊脚石,但是究竟应该怎么刷呢,相信还是有很多人不知道。
|
7月前
LeetCode hard也就这么回事
LeetCode hard也就这么回事
|
7月前
LeetCode链表hard 有思路?但写不出来?
LeetCode链表hard 有思路?但写不出来?
|
7月前
|
算法 Java
记十次面试字节/美团失败总结的《520道LeetCode题Java版答案》
去字节、美团、BAT等大厂面试,刷LeetCode上的数据结构+算法题是必修课。许多读者说,刷题的时候经常会遇到困难,想要找一本答案题解做参考。
|
7月前
|
算法 Java 程序员
太全了!字节总监总结240道算法LeetCode刷题笔记
常言道「算法才是编程的灵魂」,不管是Java, python,还是PHP,都跨不过算法这个门槛。
刷爆Leetcode!字节算法大佬进阶专属算法笔记:GitHub标星97k+
数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。 数据结构和算法是相辅相成的。数据结构是为算法服务的,算法作用在特定的数据结构之上。 因此,我们无法孤立数据结构来讲算法,也无法孤立算法来讲数据结构。
|
算法 Java 程序员
太全了!字节总监总结240道算法LeetCode刷题笔记
常言道「算法才是编程的灵魂」,不管是Java, python,还是PHP,都跨不过算法这个门槛。 许多小伙伴看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解,认为学计算机就是学各种编程语言,或者认为,学习最新的语言、技术、标准就是最好的铺路方法。