今天是LeetCode题解系列第21篇 ,今天来看一道人狠话不多的题目。 今天的题目题面非常简单,只有一句话,给定一个整数数组,要求返回小的不在数组当中的正整数。 看起来有些拗口,简单解释一下。我们都知道正整数就是从1开始的整数,所以这道题就是从1开始找到个不在数组当中的元素。我们来看下样例:
Input: [3,4,-1,1] Output: 2
Input: [7,8,9,11,12] Output: 1
分析
在后面的要求出来之前,我们可能觉得这道题也不是那么难,很容易就想到解法,但是有了这两条限制之后就没那么简单了。我们遍历数组就需要 的复杂度了,怎么还能找出小未出现的元素呢?而且还不能申请额外的数组 ,只能用常数级的存储,显然各种辅助数组和容器是不能用了。 我们直接这么苦苦思索是很难想出解法的,不如来循序渐进。 我们先来假设没有这些限制条件的话应该用什么方法,容易想到的应该是排序。我们将数组排序 ,一旦数组有序了之后就方便了。我们从小到大遍历,很容易就确定哪些元素出现过哪些元素没有。那么想要找出来不在数组当中的小自然数自然也是轻而易举。分析一下排序我们可以发现,在此过程当中我们并没有用到额外的空间,不满足条件的只有我们的时间复杂度是 而不是 。 class Solution :def firstMissingPositive (self, nums: List[int]) -> int: nums = sorted(nums)if len(nums) == or nums[ ] > 1 :return 1 mark = 1 for i in nums:if i == mark: mark += 1 return mark
那我们反过来,如果保证空间可以随意使用,但是对时间复杂度进行限制,我们能想到什么办法呢? 应该也很容易想出来,就是引入额外的容器 。比如hashset。hashset的增删改查的复杂度都可以近似看成是常数级。我们只需要遍历一次数组,将所有元素插入hashset当中,同时记录下元素的大小值,后遍历一下小值和大值这个区间,找出不在hashset当中小的元素即可。n个元素的数组我们可以很容易证明,我们一定可以在n次查找以内找到不在数组当中的自然数。 class Solution :def firstMissingPositive (self, nums: List[int]) -> int: st = set()if len(nums) == :return 1 mini, maxi = 3e9 , -3e9 # 插入set当中维护 for i in nums: st.add(i) mini = min(mini, i) maxi = max(maxi, i)# 从1开始找到个不在set当中的元素 # 由于nums只有n个元素,我们可以可以在n次遍历当中找到 for i in range(1 , maxi):if i not in st:return i# 如果从1到maxi都存在,那么就放回maxi+1和1的大值 # 因为如果maxi小于1,那么上面的循环不会执行,所以要和1取大值 return max(maxi+1 , 1 )
上面的两种做法一种进行了高复杂度的排序,另一种则用到了额外的存储。看起来这是一个两难问题,我们不想排序就需要用到存储,如果不想用存储呢,那么则需要元素有序。我们仔细分析一下这两种情况,就可以找到问题的症结了,我们有没有什么办法可以两全其美,既不用额外的存储又可以保证元素的有序呢 ?如果我们可以找到一种方法,那么这个问题就解决了。 这也是我们解题的时候的一个常规的套路,就是对于一些题目而言有一些算法是比较明显的,但是可能因为这样或那样的限制使得并不能应用在当前的问题当中。但是没关系,我们一样可以往这方面去想,先找到一个不那么合适的解法,在此基础上谋求突破,很多时候要比凭空想出一个完美的方法来容易许多。 还要从题目的要求入手,题目当中规定只能使用常数的存储空间,意味着我们不能额外开辟数组或者其他容器来存储数据。有经验的同学可能已经反映过来了,这是in-place的套路 。 in-place并不是一个算法,而是一种思想。它出现的原因也非常简单,因为我们申请数组等容器的时候需要通过操作系统向内存申请空间 ,这是需要消耗内存和时间的。所以在一些高性能的场景下,我们会希望尽量避免空间申请操作。比如我们想要对数组进行排序,我们可以拷贝数组,对拷贝出的数组排序之后返回。也就是说我们return了一个新的数组,只是其中的元素和原来一模一样。如果是in-place的方法,我们则不会另外创建数组,而在原数组上进行修改。 这个思想在机器学习当中大量用到,比如Python的numpy和pandas等库当中默认不是in-place的,这样方便数据的追踪,并且进行的改动不会覆盖原数据 ,如果一次尝试不对还可以多次尝试。而如果我们需要保证性能,我们则需要设置参数,来执行一个in-place的操作。 这题其实已经暗示得很明显了,我们需要存储数据,但是又不让我们申请空间,于是我们只有in-place一条路可以走了。 我们需要设计一个in-place的算法,让我们可以判断元素的存在性。 再加上题目中的限制是正整数,而且我们要找的是个没有出现的正整数。如果数组的长度是n,那么其实我们可以锁定,答案一定在[1, n+1]之间。 如果我们能把这个区间写出来,其实解法已经就在我们眼前了。 既然答案在区间[1, n+1]中间,我们又需要设计一个in-place的方法,那么我们可以很正常地想到,我们可以将数字放到对应的下标当中去。1放到下标1当中,0放到0当中。 比如[3, 1, 0, 5],我们拿到个元素是3,我们把它放到它应该在的位置,也就是5的位置下去,这个时候我们再来放5,由于5超过了数组的长度,所以进行丢弃。我们往下重复如上的过程,到后的时候,我们得到的数据情况如下:[0, 1, 5, 3],我们遍历一下数组,发现和下标不匹配的位置就是5,它应该对应的数据是2,所以2就是答案。 我乍看到这种算法的时候还是很惊艳的,后来想到了in-place之后,又觉得非常巧妙, 没想到利用in-place的思想还能出出这么巧妙的题。同样,如果你事先就了解过in-place的相关处理,一定也可以对这个算法理解得更加透彻。后,我们来看代码: class Solution :def firstMissingPositive (self, nums: List[int]) -> int: n = len(nums)# 因为是正整数,所以数组长度需要扩大1 nums.append( )for i in range(n):if i == nums[i]:continue while True :# 不停地交换元素,直到范围超界或者是已经放好了为止 # 需要考虑nums[i] 和 nums[nums[i]]相等的情况,这时候也不应该交换 val = nums[i]if val > n or val < or val == i or val == nums[val]:break nums[i], nums[val] = nums[val], valfor i in range(1 , n+1 ):if i != nums[i]:return ireturn n+1
后,我们来分析一下这个算法的复杂度,为什么我们在一重循环当中还套了一个while循环,但是它仍然是 的算法呢? 这个问题我们之前在介绍two pointers和尺取法的时候就曾经介绍过,我们在分析复杂度的时候不能只简单地看有几重循环 ,我们需要细致地分析。我们要忽略循环,回到问题的本质。我们用循环的本质是为了能够让每个元素放到对应的位置,一共需要安排的元素数量是固定的是n个,位置也是固定的是n个,一个元素只有一个位置。那么我们一次交换至少可以让一个元素放到正确的位置,那么问题来了,我们想要把所有元素放置好,需要循环多少次? 我这样问,大家应该很清楚,一次少放一个,一共n个,显然多放n次。那我们再看while循环当中,每执行一次,不就是放好了一个元素吗?外围的循环只是用来枚举元素的,并不会引入额外的计算,所以这当然是一个 的算法。 后,今天的题目官方标的难度是Hard,题目本身不难,由于加上了很多限制才提升了难度。题目本身并没有用到新的算法,纯粹是对思维和逻辑的考验 。也因此,我觉得它是一道非常纯粹的题,纯粹在于它并用不到新的算法,也用不到新的数据结构,就是考察我们分析问题和思考问题的能力。而许多问题则针对性很强,如果之前没有学过对应的算法则无法做得出来,所以从这点上来说这题更加公平,非常适合面试 。我已经进行了预约,以后如果有面试机会,我可能会问候选人这个问题。 今天的文章就是这些,如果觉得有所收获,请顺手点个在看或者转发 吧,你们的举手之劳对我来说很重要。