class Solution {
public:
int missingInteger(vector<int>& nums) {
}
};
100157. 大于等于顺序前缀和的最小缺失整数
给你一个下标从 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 <= 501 <= nums[i] <= 50原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2.4 MB, 提交时间: 2024-01-07 11:32:16
func missingInteger(nums []int) int {
sum := nums[0]
for i := 1; i < len(nums) && nums[i] == nums[i-1]+1; i++ {
sum += nums[i]
}
has := map[int]bool{}
for _, x := range nums {
has[x] = true
}
for has[sum] { // 至多循环 n 次
sum++
}
return sum
}
cpp 解法, 执行用时: 12 ms, 内存消耗: 19.1 MB, 提交时间: 2024-01-07 11:31:49
class Solution {
public:
int missingInteger(vector<int> &nums) {
int sum = nums[0];
for (int i = 1; i < nums.size() && nums[i] == nums[i - 1] + 1; i++) {
sum += nums[i];
}
unordered_set<int> s(nums.begin(), nums.end());
while (s.contains(sum)) { // 至多循环 n 次
sum++;
}
return sum;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 41.3 MB, 提交时间: 2024-01-07 11:31:36
class Solution {
public int missingInteger(int[] nums) {
int sum = nums[0];
for (int i = 1; i < nums.length && nums[i] == nums[i - 1] + 1; i++) {
sum += nums[i];
}
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
while (set.contains(sum)) { // 至多循环 n 次
sum++;
}
return sum;
}
}
python3 解法, 执行用时: 36 ms, 内存消耗: 16.9 MB, 提交时间: 2024-01-07 11:31:23
'''
求出最长前缀，同时维护最长前缀的元素和 sum。
不断增加 sum，直到 sum 不在 nums 中。
返回 sum。
'''
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: # 至多循环 n 次
s += 1
return s