题目描述

给你一个下标从 0 开始的整数数组 nums 。

如果一个前缀 nums[0..i] 满足对于 1 <= j <= i 的所有元素都有 nums[j] = nums[j - 1] + 1 ，那么我们称这个前缀是一个 顺序前缀 。特殊情况是，只包含 nums[0] 的前缀也是一个 顺序前缀 。

请你返回 nums 中没有出现过的 最小 整数 x ，满足 x 大于等于 最长 顺序前缀的和。

思路1:模拟

先求最长顺序前缀和,再在该和的基础上寻找最小的缺失整数。

  • 时间复杂度：
  • 空间复杂度：

代码

class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        s = nums[0]

    for x,y in pairwise(nums):
            if y != x + 1:
                break
            s += y

    st = set(nums)
        while s in st:
            s += 1

    return s