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

解法

方法一：模拟

思考

最长顺序前缀是从下标 \(0\) 起的连续递增段，其和为 \(s\)，再找不在数组中的最小 \(\ge s\) 的整数。\(n \le 50\)，先扫描前缀和，再用集合判断 \(s,s+1,\ldots\) 是否出现。

值域很小，线性递增即可碰到缺口。

我们先求出数组 \(nums\) 的最长顺序前缀和 \(s\)，然后从 \(s\) 开始枚举整数 \(x\)，如果 \(x\) 不在数组 \(nums\) 中，那么 \(x\) 就是答案。

由于题目中 \(nums[i] \leq 50\)，我们可以用一个长度为 \(51\) 的数组（或者哈希表）来记录数组中出现过的整数，从而快速判断一个整数是否在数组 \(nums\) 中。

时间复杂度 \(O(n + M)\)，空间复杂度 \(O(M)\)。其中 \(n\) 是数组 \(nums\) 的长度，而 \(M\) 是数组元素的上限，本题中 \(M = 51\)。

Python3JavaC++GoTypeScriptRust

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

class Solution {
    public int missingInteger(int[] nums) {
        int s = nums[0];
        for (int j = 1; j < nums.length && nums[j] == nums[j - 1] + 1; ++j) {
            s += nums[j];
        }
        final int m = 51;
        boolean[] st = new boolean[m];
        for (int x : nums) {
            st[x] = true;
        }
        while (s < m && st[s]) {
            ++s;
        }
        return s;
    }
}

class Solution {
public:
    int missingInteger(vector<int>& nums) {
        int s = nums[0];
        for (int j = 1; j < nums.size() && nums[j] == nums[j - 1] + 1; ++j) {
            s += nums[j];
        }

        const int m = 51;
        bool st[m] = {};
        for (int x : nums) {
            st[x] = true;
        }

        while (s < m && st[s]) {
            ++s;
        }
        return s;
    }
};

func missingInteger(nums []int) int {
    s := nums[0]
    for j := 1; j < len(nums) && nums[j] == nums[j-1]+1; j++ {
        s += nums[j]
    }

    const m = 51
    st := make([]bool, m)
    for _, x := range nums {
        st[x] = true
    }

    for s < m && st[s] {
        s++
    }
    return s
}

function missingInteger(nums: number[]): number {
    let s = nums[0];
    for (let j = 1; j < nums.length && nums[j] === nums[j - 1] + 1; ++j) {
        s += nums[j];
    }

    const m = 51;
    const st = new Array<boolean>(m).fill(false);
    for (const x of nums) {
        st[x] = true;
    }

    while (s < m && st[s]) {
        ++s;
    }
    return s;
}

impl Solution {
    pub fn missing_integer(nums: Vec<i32>) -> i32 {
        let mut s = nums[0];

        for j in 1..nums.len() {
            if nums[j] != nums[j - 1] + 1 {
                break;
            }
            s += nums[j];
        }

        const M: usize = 51;
        let mut st = [false; M];

        for &x in &nums {
            st[x as usize] = true;
        }

        while s < M as i32 && st[s as usize] {
            s += 1;
        }

        s
    }
}

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

题目描述

解法

方法一：模拟

评论