2996. 大于等于顺序前缀和的最小缺失整数

题目

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

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

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

示例 1：

输入：nums = [1,2,3,2,5]
输出：6
解释：nums 的最长顺序前缀是 [1,2,3] ，和为 6 ，6 不在数组中，所以 6 是大于等于最长顺序前缀和的最小整数。

示例 2：

输入：nums = [3,4,5,1,12,14,13]
输出：15
解释：nums 的最长顺序前缀是 [3,4,5] ，和为 12 ，12、13 和 14 都在数组中，但 15 不在，所以 15 是大于等于最长顺序前缀和的最小整数。

提示：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50

解答

class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        # 求最长连续递增前缀的元素和
        s = nums[0]
        for i in range(1, len(nums)):
            if nums[i - 1] + 1 != nums[i]:
                break
            s += nums[i]
        ...

更加 Python 的写法：

class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        # 求最长连续递增前缀的元素和
        s = nums[0]
        for x, y in pairwise(nums):
            if x + 1 != y:
                break
            s += y
        ...

pairwise() 函数

• from itertools import pairwise 导入头文件
• itertools.pairwise(iterable)
• 创建一个迭代器，返回从 iterable 获取的连续重叠对

>>> from itertools import pairwise

>>> pairwise('ABCDEFG')
<itertools.pairwise at 0x20bd0d69a20>

>>> for i in pairwise('ABCDEFG'):
>>>     print(i)
('A', 'B')
('B', 'C')
('C', 'D')
('D', 'E')
('E', 'F')
('F', 'G')

>>> for i in pairwise([1, 2, 3, 4, 5]):
>>>     print(i)
(1, 2)
(2, 3)
(3, 4)
(4, 5)

还需要 nums[] 中没有出现过这个整数 x，因此总体代码为：

class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        # 求最长连续递增前缀的元素和
        s = nums[0]
        for x, y in pairwise(nums):
            if x + 1 != y:
                break
            s += y

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

        return s

set() 的用法

• set(iterable) 集合类的参数必须是可迭代类型的，例如 list, dict, tuple 等
  • 创建空集合 set()
  • 创建非空集合，当参数为字典时，只取了字典的 key，相当于 set(dict.key)) 将键的列表转成集合
• 添加操作：
  • add() 方法，把要传入的元素作为一个整体添加到集合中
  • update() 方法，把要传入的元素当作 iterable 类型，拆分后添加到集合
• 删除方法：
  • remove(element) 方法，删除指定元素，没找到则报错
  • discard(element) 方法，删除指定元素，没找到则什么也不做
• 遍历方法：
  • for i in s
  • for idx, i in enumerate(s) 其中 idx 是索引，i 是集合中的元素
• 集合运算：
  • s1 & s2 交集
  • s1 | s2 并集
  • s1 - s2 差集，等价于 s1.difference(s2)
  • s1 ^ s2 对称差集
• 集合的范围判断：
  • >, >= 左边集合是否完全包含右边集合
  • <, <= 右边集合是否完全包含左边集合
  • ==, != 集合是否相等
• 不可变集合 frozenset()，用法同 set()，只读集合，不能修改元素

时间复杂度

$O(n)$