Easy

题目描述

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

如果对于所有 1 <= j <= i，都有 nums[j] = nums[j - 1] + 1，那么我们称前缀 nums[0..i] 是 序列化的。特别地，只包含 nums[0] 的前缀也是序列化的。

返回数组中缺失的最小整数 x，满足 x 大于或等于最长序列化前缀的和。

示例 1：

输入：nums = [1,2,3,2,5]
输出：6
解释：最长的序列化前缀是 [1,2,3]，和为 6。6 不在数组中，因此 6 是大于或等于最长序列化前缀和的最小缺失整数。

示例 2：

输入：nums = [3,4,5,1,12,14,13]
输出：15
解释：最长的序列化前缀是 [3,4,5]，和为 12。12、13 和 14 都在数组中，而 15 不在。因此 15 是大于或等于最长序列化前缀和的最小缺失整数。

提示：

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

解题思路

这道题需要分两个步骤解决：

  1. 找到最长序列化前缀并计算和：从数组开头开始遍历，只要当前元素比前一个元素大1，就继续扩展前缀。一旦遇到不连续的元素，前缀就结束了。

  2. 寻找缺失的最小整数：从前缀和开始，逐个检查整数是否存在于原数组中。第一个不存在的整数就是答案。

具体实现思路：

  • 首先遍历数组找到最长序列化前缀的长度，并计算其和
  • 将数组元素存入哈希集合以便快速查找
  • 从前缀和开始向上查找，直到找到第一个不在数组中的数

时间复杂度主要取决于寻找缺失数字的过程，由于数组长度和元素值都不超过50，最坏情况下也只需要检查有限次。

推荐解法：使用哈希集合优化查找过程，确保每次检查数字是否存在的时间复杂度为O(1)。

代码实现

class Solution {
public:
    int missingInteger(vector<int>& nums) {
        // 找到最长序列化前缀的和
        int sum = nums[0];
        int i = 1;
        while (i < nums.size() && nums[i] == nums[i-1] + 1) {
            sum += nums[i];
            i++;
        }
        
        // 将数组元素存入哈希集合
        unordered_set<int> numSet(nums.begin(), nums.end());
        
        // 从sum开始找缺失的最小整数
        while (numSet.count(sum)) {
            sum++;
        }
        
        return sum;
    }
};

class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        # 找到最长序列化前缀的和
        sum_val = nums[0]
        i = 1
        while i < len(nums) and nums[i] == nums[i-1] + 1:
            sum_val += nums[i]
            i += 1
        
        # 将数组元素存入集合
        num_set = set(nums)
        
        # 从sum_val开始找缺失的最小整数
        while sum_val in num_set:
            sum_val += 1
        
        return sum_val

public class Solution {
    public int MissingInteger(int[] nums) {
        // 找到最长序列化前缀的和
        int sum = nums[0];
        int i = 1;
        while (i < nums.Length && nums[i] == nums[i-1] + 1) {
            sum += nums[i];
            i++;
        }
        
        // 将数组元素存入哈希集合
        HashSet<int> numSet = new HashSet<int>(nums);
        
        // 从sum开始找缺失的最小整数
        while (numSet.Contains(sum)) {
            sum++;
        }
        
        return sum;
    }
}

var missingInteger = function(nums) {
    // 找到最长序列化前缀的和
    let sum = nums[0];
    let i = 1;
    while (i < nums.length && nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n + k)，其中 n 是数组长度，k 是寻找缺失数字的次数（最坏情况下 k ≤ 50）
空间复杂度O(n)，用于存储哈希集合

相关题目