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
解答
python
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 的写法:
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
获取的连续重叠对
python
>>> 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
,因此总体代码为:
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
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()
,只读集合,不能修改元素
时间复杂度