Easy

题目描述

给你一个 严格升序排列 的正整数数组 arr 和一个整数 k。

请你找到这个数组里第 k 个缺失的正整数。

示例 1：

输入：arr = [2,3,4,7,11], k = 5
输出：9
解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...]。第 5 个缺失的正整数为 9。

示例 2：

输入：arr = [1,2,3,4], k = 2
输出：6
解释：缺失的正整数包括 [5,6,7,...]。第 2 个缺失的正整数为 6。

提示：

  • 1 <= arr.length <= 1000
  • 1 <= arr[i] <= 1000
  • 1 <= k <= 1000
  • 对于 1 <= i < j <= arr.length，有 arr[i] < arr[j]

进阶： 你可以设计一个时间复杂度小于 O(n) 的算法来解决此问题吗？

解题思路

解题思路

这道题要求找到数组中第 k 个缺失的正整数。我们可以用两种方法来解决：

方法一：线性扫描（推荐）

最直观的思路是遍历数组，同时维护一个期望值 expected，表示当前位置应该出现的正整数。如果当前数组元素等于期望值，说明没有缺失；否则说明有缺失的数字，我们需要统计缺失的个数。

具体步骤：

  1. 初始化期望值为 1，缺失计数为 0
  2. 遍历数组，对于每个元素，计算它前面缺失了多少个正整数
  3. 如果缺失数量达到 k，直接返回对应的缺失数字
  4. 如果遍历完数组还没找到，说明第 k 个缺失数字在数组最后一个元素之后

方法二：二分查找

对于进阶要求，我们可以使用二分查找。关键观察是：对于数组中位置 i 的元素 arr[i]，在它之前缺失的正整数个数为 arr[i] - (i + 1)。我们可以二分查找第一个缺失数量大于等于 k 的位置。

时间复杂度：线性扫描 O(n)，二分查找 O(log n)

代码实现

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int expected = 1;
        int missing = 0;
        
        for (int num : arr) {
            missing += num - expected;
            if (missing >= k) {
                return num - (missing - k + 1);
            }
            expected = num + 1;
        }
        
        return arr.back() + (k - missing);
    }
};

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        expected = 1
        missing = 0
        
        for num in arr:
            missing += num - expected
            if missing >= k:
                return num - (missing - k + 1)
            expected = num + 1
        
        return arr[-1] + (k - missing)

public class Solution {
    public int FindKthPositive(int[] arr, int k) {
        int expected = 1;
        int missing = 0;
        
        foreach (int num in arr) {
            missing += num - expected;
            if (missing >= k) {
                return num - (missing - k + 1);
            }
            expected = num + 1;
        }
        
        return arr[arr.Length - 1] + (k - missing);
    }
}

var findKthPositive = function(arr, k) {
    let expected = 1;
    let missing = 0;
    
    for (let num of arr) {
        missing += num - expected;
        if (missing >= k) {
            return num - (missing - k + 1);
        }
        expected = num + 1;
    }
    
    return arr[arr.length - 1] + (k - missing);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
线性扫描O(n)O(1)
二分查找O(log n)O(1)

相关题目