题目描述
给你一个下标从 0 开始的整数数组 nums
。
如果一个前缀 nums[0..i]
满足对于 1 <= j <= i
的所有元素都有 nums[j] = nums[j - 1] + 1
,那么我们称这个前缀是一个 顺序前缀。特殊情况是,只包含 nums[0]
的前缀也是一个 顺序前缀。
请你返回 nums
中没有出现过的 最小 整数 x
,满足 x
大于等于 最长 顺序前缀的和。
样例
输入:nums = [1,2,3,2,5]
输出:6
解释:nums 的最长顺序前缀是 [1,2,3],和为 6,6 不在数组中,所以 6 是大于等于最长顺序前缀和的最小整数。
输入: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
算法
(哈希表,枚举) $O(n)$
- 先根据题意,求出最长顺序前缀的和 $ans$。
- 然后使用哈希表判断 $ans$ 是否在数组中出现过,如果出现过,则不断累加 $ans$,直到满足题意。
时间复杂度
- 求最长顺序前缀和的时间复杂度为 $O(n)$。
- 累加 $ans$ 最多 $n$ 次。
- 故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表。
C++ 代码
class Solution {
public:
int missingInteger(vector<int>& nums) {
unordered_set<int> seen(nums.begin(), nums.end());
const int n = nums.size();
int ans = nums[0];
for (int i = 1; i < n; i++) {
if (nums[i] != nums[i - 1] + 1)
break;
ans += nums[i];
}
while (seen.find(ans) != seen.end())
++ans;
return ans;
}
};