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

难度:

标签:

题目描述

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

代码结果

运行时间: 20 ms, 内存: 15.9 MB

/*
 * 思路：
 * 1. 使用Java Stream找到最长的顺序前缀。
 * 2. 计算该前缀的和。
 * 3. 使用Stream找到大于等于该和且不在数组中的最小整数。
 */
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int minImpossibleSum(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        int longestPrefixLength = (int) Arrays.stream(nums)
                .takeWhile((v, i) -> i == 0 || nums[i] == nums[i - 1] + 1)
                .count();

        int prefixSum = Arrays.stream(nums, 0, longestPrefixLength + 1).sum();
        numSet.addAll(Arrays.stream(nums).boxed().toList());
        
        return Arrays.stream(nums)
                .mapToInt(i -> i)
                .filter(i -> i >= prefixSum && !numSet.contains(i))
                .findFirst()
                .orElse(prefixSum);
    }
}

解释

方法:

题解首先通过遍历数组nums来寻找最长的顺序前缀，并计算这个顺序前缀的和s。顺序前缀是指数组的一个片段，其中每个元素都比前一个元素大1。一旦找到了顺序前缀，算法就会停止累加s。接下来，算法使用一个无限循环来寻找大于等于s的最小的不在数组nums中的整数。循环中，如果s在数组中，s就递增1，否则返回s作为结果，因为这是第一个不在数组中且大于等于顺序前缀和的整数。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

题解中提到寻找最长顺序前缀，并计算和。请问如果数组中所有元素都是顺序的，算法是否有必要检查每个元素是否满足顺序条件，能否优化此过程？

▷

如果已知数组中所有元素都严格顺序递增，每个元素确实都是前一个元素加1，那么算法中检查每个元素是否满足顺序条件的步骤可以简化。例如，可以直接使用数组的长度和首元素计算整个数组的和，即 s = n * (首元素 + 末元素) / 2，这里的 n 是数组的长度。这种方法利用等差数列求和公式，避免了逐一检查每个元素，从而优化了计算过程。

🦆

算法在寻找最小的不在数组中的大于等于s的整数时，使用了`while True`循环，这种做法是否会有潜在的效率问题，尤其是当数组很大时？

▷

使用 `while True` 循环确实可能存在效率问题，特别是在数组很大或者大于等于 s 的最小缺失整数远大于数组中的最大值时。每次循环都需要检查 s 是否在数组中，这个操作的时间复杂度是 O(n)，其中 n 是数组长度。因此，总的时间复杂度可能高达 O(n*m)，其中 m 是从 s 开始直到找到不在数组中的第一个整数的次数。为了优化这一过程，可以先将数组元素存储在哈希表中，这样检查一个元素是否在数组中的时间复杂度降为 O(1)，从而显著提高整体效率。

🦆

题解中未使用额外的数据结构来优化查找过程。在实际应用中，使用哈希表来存储数组元素是否会更高效？如果会，为什么？

▷

是的，使用哈希表来存储数组元素会更高效。哈希表支持平均时间复杂度为 O(1) 的查找操作，这可以显著提高检查一个整数是否存在于数组中的效率。与直接在数组中查找每个元素相比（平均时间复杂度为 O(n)），哈希表可以减少查找时间，特别是在多次查找操作时尤为明显。此外，构建哈希表的时间复杂度为 O(n)，因此整体时间复杂度为 O(n)，这在多次查询的情况下是优于直接搜索的。

🦆

算法中断开顺序前缀的判断是`nums[i] != nums[i-1] + 1`，这种情况是否包括了数组中出现的任何非顺序元素，比如重复或者更大跳跃的情况？

▷

是的，条件 `nums[i] != nums[i-1] + 1` 包括了任何导致顺序被打断的情况，无论是数字的重复还是更大的跳跃。此条件确保只有当当前元素正好是前一个元素加1时顺序才继续。任何其他情况，如元素相同（重复）或当前元素大于前一个元素加1的情况（大跳跃），都会导致循环终止，因为这些情况都不满足严格递增的顺序要求。

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

题目描述

代码结果

解释

代码细节讲解

相关问题