第 k 个缺失的正整数

难度:

标签:

题目描述

代码结果

运行时间: 18 ms, 内存: 16.1 MB

/*
 * 思路：
 * 使用流操作计算数组中每个数字的缺失数字数量，
 * 并在其中找到第 k 个缺失的数字。
 */
import java.util.Arrays;

public class Solution {
    public int findKthPositive(int[] arr, int k) {
        return Arrays.stream(arr)
            .boxed()
            .reduce(0, (missing, current) -> {
                int expected = missing + 1;
                if (expected < current) {
                    int missingCount = current - expected;
                    if (k <= missingCount) {
                        return missing + k;
                    }
                    k -= missingCount;
                }
                return current;
            }, (a, b) -> a) + k;
    }
}

解释

方法:

该题解采用了一种逐个检查的方法。首先，通过设置一个外部计数器 count 来遍历所有自然数，然后与数组 arr 中的元素进行比较。如果当前的 count 值不在 arr 中，即认为这是一个缺失的正整数，此时增加缺失计数器 n。一旦 n 达到 k，即找到了第 k 个缺失的正整数。如果整个数组都遍历完毕，但是缺失的数还没找完，就继续增加 count，直到找到第 k 个缺失的正整数。

时间复杂度:

O(k + n)

空间复杂度:

O(1)

代码细节讲解

🦆

在遍历数组时，你是如何处理数组中连续多个数字缺失的情况，比如在数组 [2, 5] 中找第 3 个缺失的正整数？

▷

在给定数组 [2, 5] 中，算法从 count = 1 开始逐个检查每个自然数。首先发现 1 缺失（因为 count = 1 且 1 不等于 2），此时缺失计数器 n 增加 1。接着 count 增加到 2，发现 2 存在于数组，于是跳过。然后 count 增加到 3，发现 3 缺失（因为 3 不等于 5），n 增加 1。同理，4 也缺失，n 再增加 1。当 n 达到 3 时，此时 count = 4，算法将返回 4 作为第 3 个缺失的正整数。因此，算法能有效处理连续缺失数字的情况。

🦆

如果输入的数组 arr 中的最大数字非常接近 1000，而 k 还很大，比如 k = 100，你的方法是否还是有效？是否存在性能优化的可能？

▷

该方法在处理大数组和大 k 值时依然有效，但效率可能不是最优的。尤其当 arr 的最大值接近 1000 而 k 也很大时，该方法需要遍历大量的数字直到找到第 k 个缺失的正整数，这可能导致较高的时间复杂度。性能优化可以考虑使用二分查找来加速确定缺失的正整数的位置，通过比较每个元素与其索引的差值来估算缺失数字的数量，从而减少需要检查的数字数量。

🦆

为什么在遍历完数组后，还需要一个额外的 while 循环来继续寻找缺失的正整数？

▷

在遍历完数组后，如果没有找到第 k 个缺失的正整数，这意味着第 k 个缺失的数字大于数组中的任何元素。此时，需要继续递增 count，同时更新缺失计数器 n，直到 n 等于 k。这个额外的 while 循环确保即使在数组元素之后仍可以找到缺失的数字，因为缺失的正整数可能会出现在数组的最大值之后。

🦆

你的解法在数组元素非常稠密，比如 arr = [1,2,3,...,999]，且 k = 1 的情况下性能如何？

▷

在数组元素非常稠密时，特别是当数组几乎包含了所有连续的数字，本算法的性能仍然有效，但不是最优的。以 arr = [1, 2, 3, ..., 999] 和 k = 1 为例，算法需要遍历整个数组，直到 count 达到 1000，并且发现 1000 不在数组中时，才能够返回 1000 作为第一个缺失的正整数。这种情况下，算法的时间复杂度与数组的长度直接相关，因此在极端情况下（如稠密数组），效率较低。

第 k 个缺失的正整数

题目描述

代码结果

解释

代码细节讲解

相关问题