「脸书」我接着刷 41 ～ 第一个缺失的正书

基本信息

• 题号：41
• 题厂：脸书
• 难度系数：高

一个无序数组里混合正数、负数，0，问数组确实的第一个正数是啥？？

例如 nums = [1,2,0]
返回 3，因为 1、2 均存在

nums = [3,4,-1,1] 返回 2，1 存在，但是没有 2

1 排序

• 可以先将数组「排序」，再遍历一遍数组。当前元素小于等于 0，自动过滤；遇到正数后往下计数，如果接不上，说明遇上缺失正数，即可返回。
• 遍历完结后依然没有返回，说明这是一个完整的数组。即数组长度为 2，包含元素也为 1 和 2，所以返回 3（数组长度 + 1）。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        nums.sort()
        res = 1

        for n in nums:
            if n > 0 and n > res:
                return res
            elif n > 0 and n == res:
                res += 1

        return res

2 extra space mark

• 如果不采用排序，另一种解法是创建一个和数组长度对等的空数组。
• 遍历数组，遇上正数，在对应 「val - 1」 的 index 处标记。
• 再次遍历数组，遇上标记好的 mark 后即可返回……

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        container = [0] * len(nums)

        for n in nums:
            if 0 < n <= len(nums):
                container[n - 1] = n

        for i in range(len(container)):
            if container[i] == 0:
                return i + 1

        return len(container) + 1

以上 1 、 2 两种解法，顶多就算一道正常难度，甚至偏简单的考题。最多十分种即可解决问题。根本不算难题，本题的难点在于：时间复杂度 O（n）；空间复杂度O（1）。

当我们采用 1 号排序算法时，复杂度为 O（nlogn）；采用 2 号解法时，虽然满足了时间复杂度 O（n），但空间复杂度又上升到了 O（n）

解题思路

在满足时间空间复杂度的前提下解此题，可以参考 #448。这里运用正负号在输入数组内进行标记，从而同时满足时间复杂度 O（n）空间复杂度 O（1）的题目要求。

除了正负号，还要运用 val 和 index 的数学关联性。如果当前数组长度为 n，如果数组内不出现缺失正数的情况是，元素 1 ～ n 递增……

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # 第一轮遍历，将所有负数标记为 0
        for i in range(len(nums)):
            if nums[i] < 0:
                nums[i] = 0
        
        # 第二轮遍历，如果遇上正数，需要在对应「n - 1」的位置用负数标记
        for n in nums:
            val = abs(n)
            if 0 < val <= len(nums):
                if nums[val - 1] > 0:
                    nums[val - 1] = -1 * nums[val - 1]
                elif nums[val - 1] == 0:
                    nums[val - 1] = -1 * val

        # 第三轮遍历，遇上正书，说明该位置空缺，即可返回跳出循环
        for i in range(len(nums)):
            if nums[i] >= 0:
                return i + 1

        return len(nums) + 1

Constraints

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

做题前要和考官讨论取值范围，数字可否重复出现等

测试

• n = 1 时
• 1 ～ n 全部对应出现无缺失时
• 当有缺失时：正负数大混合，只有正数但不为 1 ～ n 连续
• ……

Big O

• 时间复杂度：O（n）
• 空间复杂度： O（1）

总结

• 这是一道扩展性极大的题，非常具有研究价值
• 做出 1、2 解法者，为入门级码工；但要奋斗「歌脸软麻年薪百万者」，需熟练最优解且思维灵活懂得扩展
• 虽然这是一道难题，但充分体现了难题由中档题升级变形的思想。