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

土豆炒青椒
·
(修改过)
·
IPFS
继续吐血刷题系列

基本信息

  • 题号: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 解法者,为入门级码工;但要奋斗「歌脸软麻年薪百万者」,需熟练最优解且思维灵活懂得扩展
  • 虽然这是一道难题,但充分体现了难题由中档题升级变形的思想。
CC BY-NC-ND 2.0 授权

喜欢我的作品吗?别忘了给予支持与赞赏,让我知道在创作的路上有你陪伴,一起延续这份热忱!