LeetCode 1060. 有序数组中的缺失元素

Categories:

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

题目描述

✅ 1060. 有序数组中的缺失元素

思路分析

解法一：二分查找（推荐）

核心思路：

定义缺失数量 missing(i) = nums[i] - nums[0] - i。

若 k 大于最后一位的缺失数，答案在数组末尾之后。

否则二分找到最小下标使缺失数 ≥ k。

复杂度分析：

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

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

class Solution {
    public int missingElement(int[] nums, int k) {
        int n = nums.length;
        int totalMissing = nums[n - 1] - nums[0] - (n - 1);
        if (k > totalMissing) {
            return nums[n - 1] + (k - totalMissing);
        }

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

        int missingBefore = nums[left - 1] - nums[0] - (left - 1);
        return nums[left - 1] + (k - missingBefore);
    }
}

func missingElement(nums []int, k int) int {
	n := len(nums)
	totalMissing := nums[n-1] - nums[0] - (n - 1)
	if k > totalMissing {
		return nums[n-1] + (k - totalMissing)
	}

	left, right := 0, n-1
	for left < right {
		mid := left + (right-left)/2
		missing := nums[mid] - nums[0] - mid
		if missing >= k {
			right = mid
		} else {
			left = mid + 1
		}
	}

	missingBefore := nums[left-1] - nums[0] - (left - 1)
	return nums[left-1] + (k - missingBefore)
}

相似题目

题目	难度	考察点
1539. 第 k 个缺失的正整数	简单	二分
704. 二分查找	简单	二分
35. 搜索插入位置	简单	二分
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分
852. 山脉数组的峰顶索引	简单	二分

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/64759297