1539. 第 k 个缺失的正整数

🟢   🔖  数组 二分查找  🔗 力扣 LeetCode

题目

Given an array arr of positive integers sorted in a strictly increasing order , and an integer k.

Return the kth positive integer that is missing from this array.

Example 1:

Input: arr = [2,3,4,7,11], k = 5

Output: 9

Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2

Output: 6

Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

Constraints:

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 1000
• 1 <= k <= 1000
• arr[i] < arr[j] for 1 <= i < j <= arr.length

Follow up:

Could you solve this problem in less than O(n) complexity?

题目大意

给你一个 严格升序排列 的正整数数组 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 的 i 和 j 满足 arr[i] < arr[j]

进阶：

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

解题思路

1. 对于任意索引 i，数组中小于等于 arr[i] 的正整数的数量是 arr[i]，则从 1 到 arr[i] 中缺失的正整数数量为：missing(i) = arr[i] - i - 1。

2. 可以使用二分查找来定位第 k 个缺失数字在哪个索引范围内：

   • 如果在索引 mid 前缺失的数字总数 missing(mid) < k，说明目标在右边，调整 left = mid + 1。
   • 如果 missing(mid) >= k，说明目标在左边或当前范围内，调整 right = mid。

3. 最终搜索结束时，第 k 个缺失的数字在 (arr[left - 1], arr[left]) 范围内。

4. 计算结果

   • 由上可知，在 arr[left - 1] 之前缺失的正整数数量为： missing(left - 1) = arr[left - 1] - (left - 1) - 1
   • 因此，在 arr[left - 1] 之后，还需要再数 k - missing(left - 1) 个数；
   • 因此，缺失的第 k 个数字为： result = arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1)
   • 可以化简为： result = k + left

复杂度分析

• 时间复杂度：O(log n)，其中 n 是 arr 长度，，二分查找每次搜索将范围缩小一半，最多进行 O(log n) 次比较。
• 空间复杂度：O(1)，只使用了常数个额外变量。

代码

var findKthPositive = function (arr, k) {
	let left = 0,
		right = arr.length;
	while (left < right) {
		const mid = Math.floor((left + right) / 2);
		if (arr[mid] - mid - 1 < k) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	// 第 k 个缺失数字为 k + left
	return k + left;
};

相关题目

题号	标题	题解	标签	难度	力扣
2195	向数组中追加 K 个整数		贪心 数组 数学 1+	🟠	🀄️ 🔗