LeetCode 1539. 第 k 个缺失的正整数

Categories:

题目描述
思路分析
1. 解法一：二分查找缺失数量（推荐）
相似题目

题目描述

✅ 1539. 第 k 个缺失的正整数

思路分析

解法一：二分查找缺失数量（推荐）

核心思路：

对于有序数组 arr，索引 i 处缺失的数量为 arr[i] - (i + 1)。

通过二分找到最小的 i 使缺失数量 >= k。

结果为 k + i。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int n = arr.length;
        int left = 0;
        int right = n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int missing = arr[mid] - (mid + 1);
            if (missing < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return k + left;
    }
}

func findKthPositive(arr []int, k int) int {
	left, right := 0, len(arr)-1
	for left <= right {
		mid := left + (right-left)/2
		missing := arr[mid] - (mid + 1)
		if missing < k {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return k + left
}

相似题目

题目	难度	考察点
35. 搜索插入位置	简单	二分查找
704. 二分查找	简单	二分查找
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分查找
278. 第一个错误的版本	简单	二分查找
374. 猜数字大小	简单	二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/61279291