Question

2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

中文文档

Description

You are given a 0-indexed array of integers nums.

A prefix nums[0..i] is sequential if, for all 1 <= j <= i, nums[j] = nums[j - 1] + 1. In particular, the prefix consisting only of nums[0] is sequential.

Return _the smallest integer_ x _missing from_ nums _such that_ x _is greater than or equal to the sum of the longest sequential prefix._

 

Example 1:

Input: nums = [1,2,3,2,5]
Output: 6
Explanation: The longest sequential prefix of nums is [1,2,3] with a sum of 6. 6 is not in the array, therefore 6 is the smallest missing integer greater than or equal to the sum of the longest sequential prefix.

Example 2:

Input: nums = [3,4,5,1,12,14,13]
Output: 15
Explanation: The longest sequential prefix of nums is [3,4,5] with a sum of 12. 12, 13, and 14 belong to the array while 15 does not. Therefore 15 is the smallest missing integer greater than or equal to the sum of the longest sequential prefix.

 

Constraints:

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

Solutions

Solution 1: Simulation + Hash Table

First, we calculate the longest prefix sum $s$ of the array $nums$. Then, starting from $s$, we enumerate the integer $x$. If $x$ is not in the array $nums$, then $x$ is the answer. Here, we can use a hash table to quickly determine whether an integer is in the array $nums$.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array $nums$.

class Solution:
  def missingInteger(self, nums: List[int]) -> int:
    s, j = nums[0], 1
    while j < len(nums) and nums[j] == nums[j - 1] + 1:
      s += nums[j]
      j += 1
    vis = set(nums)
    for x in count(s):
      if x not in vis:
        return x

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];
    }
    boolean[] vis = new boolean[51];
    for (int x : nums) {
      vis[x] = true;
    }
    for (int x = s;; ++x) {
      if (x >= vis.length || !vis[x]) {
        return x;
      }
    }
  }
}

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];
    }
    bitset<51> vis;
    for (int x : nums) {
      vis[x] = 1;
    }
    for (int x = s;; ++x) {
      if (x >= 51 || !vis[x]) {
        return x;
      }
    }
  }
};

func missingInteger(nums []int) int {
  s := nums[0]
  for j := 1; j < len(nums) && nums[j] == nums[j-1]+1; j++ {
    s += nums[j]
  }
  vis := [51]bool{}
  for _, x := range nums {
    vis[x] = true
  }
  for x := s; ; x++ {
    if x >= len(vis) || !vis[x] {
      return x
    }
  }
}

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 vis: Set<number> = new Set(nums);
  for (let x = s; ; ++x) {
    if (!vis.has(x)) {
      return x;
    }
  }
}