LeetCode 41，一题解读in-place思想

今天是 LeetCode题解系列第21篇 ，今天来看一道人狠话不多的题目。

题面

题目非常简单，只有一句话，给定一个整数数组，要求返回最小的不在数组当中的正整数。

看起来有些拗口，简单解释一下。我们都知道正整数就是从1开始的整数，所以这道题就是从1开始找到第一个不在数组当中的元素。我们来看下样例：

样例 1:

Input: [1,2,0]
Output: 3

样例 2:

Input: [3,4,-1,1]
Output: 2

样例 3:

Input: [7,8,9,11,12]
Output: 1

注意:

算法的 时间复杂度 必须是 ，并且只能使用 的存储空间。

分析

在注意出来之前，我们可能觉得这道题也不是那么难，很容易就想到解法，但是有了这两条限制之后就没那么简单了。我们遍历数组就需要 的复杂度了，怎么还能找出最小未出现的元素呢？而且还不能申请额外的数组，只能用常数级的存储，显然各种辅助数组和容器是不能用了。

我们直接这么苦苦思索是很难想出解法的，不如来 循序渐进 。

我们先来假设没有这些限制条件的话应该用什么方法，最容易想到的应该是 排序 。我们将数组排序，一旦数组有序了之后就方便了。我们从小到大遍历，很容易就确定哪些元素出现过哪些元素没有。那么想要找出来不在数组当中的最小自然数自然也是轻而易举。分析一下排序我们可以发现，在此过程当中我们并没有用到额外的空间，唯一不满足条件的只有我们的时间复杂度是 而不是 。

我们写下代码：

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        nums = sorted(nums)
        if len(nums) == 0 or nums[0] > 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) == 0:
            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的套路 。

in-place并不是一个算法，而是一种思想。它出现的原因也非常简单，因为我们申请数组等容器的时候需要 通过操作系统向内存申请连续的内存 ，这会涉及到一系列内存管理算法的执行，所以是需要 消耗大量时间 的。所以在一些高性能的场景下，我们会希望尽量避免空间申请操作。

比如我们想要对数组进行排序，我们直接调用sorted方法的时候，其实在函数内部对数组进行了拷贝，最后返回的其实是拷贝数组排序之后的结果。也就是说我们 获得的是一个新的数组 ，只是其中的元素和原来一模一样。而如果是in-place的方法，我们则不会另外创建数组，而在原数组上进行修改。

非in-place的接口不会修改原值，这方便我们追踪数据的变化，以及撤销操作。比如Python机器学习领域的大量numpy和pandas的接口默认都不是in-place的，就是这个原因。而in-place的则相反，由于它会直接修改原值，所以如果我们一旦执行错了，无法撤销，原数据就找不回了。比如我们排序错了，明明要降序，不小心排成了升序，一旦执行就无法还原了。但是和非in-place相比，它的 耗时更少，也更节约内存 。

这题其实已经暗示得很明显了，我们需要存储数据，但是又不让我们申请空间，于是我们只有in-place一条路可以走了。

我们需要设计一个in-place的算法，让我们可以判断元素的存在性。再加上题目中的限制是正整数，而且我们要找的是第一个没有出现的正整数。如果数组的长度是n，那么其实我们可以锁定， 答案一定在[1, n+1]之间 。原因也很简单，因为最理想的情况是这个数组当中的n个元素刚好是1到n，这样我们从1开始遍历，一直找到n就能得到答案是n+1。否则的话，我们一定可以在遍历到n+1之前就找到答案，所以综合一下，答案一定在[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思想之后，才发现隐藏的思路其实非常合情合理。思路有了，代码真的很简单：

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        # 因为是正整数，所以数组长度需要扩大1
        nums.append(0)
        
        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 < 0 or val == i or val == nums[val]:
                    break
                nums[i], nums[val] = nums[val], val
                
        
        for i in range(1, n+1):
            if i != nums[i]:
                return i
            
        return n+1
                

最后，我们来分析一下这个算法的复杂度，为什么我们在一重循环当中还套了一个while循环，但是它仍然是 的算法呢？

这个问题我们之前在介绍two pointers和尺取法的时候就曾经介绍过，我们在分析复杂度的时候 不能只简单地看有几重循环 ，我们需要细致地分析。我们要忽略循环，回到问题的本质。我们用循环的本质是为了能够让每个元素放到对应的位置，一共需要安排的元素数量是固定的是n个，位置也是固定的是n个，一个元素只有一个位置。那么我们一次交换至少可以让一个元素放到正确的位置，那么问题来了，我们想要把所有元素放置好，需要循环多少次？

我这样问，大家应该很清楚，一次最少放一个，一共n个，显然最多放n次。那我们再看while循环当中，每执行一次，不就是放好了一个元素吗？外围的循环只是用来枚举元素的，并不会引入额外的计算，所以这当然是一个 的算法。

最后，今天的题目官方标的难度是Hard，题目本身不难，由于加上了很多限制才提升了难度。今天的题目没有用到新的算法，纯粹是对思维和逻辑的考验。也因此，我觉得它是一道非常纯粹的题，纯粹在于它并用不到新的算法，也用不到新的数据结构，就是考察我们分析问题和思考问题的能力。而许多问题则针对性很强，如果之前没有学过对应的算法则无法做得出来，所以从这点上来说这题 更加公平，非常适合面试 。我已经进行了预约，以后如果有面试机会，我可能会问候选人这个问题。

今天的文章就是这些，如果觉得有所收获，请顺手点个 关注或者转发 吧，你们的举手之劳对我来说很重要。