Question

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

English Version

题目描述

现有一个按 升序 排列的整数数组 nums ，其中每个数字都 互不相同 。

给你一个整数 k ，请你找出并返回从数组最左边开始的第 k 个缺失数字。

 

示例 1：

输入：nums = [4,7,9,10], k = 1
输出：5
解释：第一个缺失数字为 5 。

示例 2：

输入：nums = [4,7,9,10], k = 3
输出：8
解释：缺失数字有 [5,6,8,...]，因此第三个缺失数字为 8 。

示例 3：

输入：nums = [1,2,4], k = 3
输出：6
解释：缺失数字有 [3,5,6,7,...]，因此第三个缺失数字为 6 。

 

提示：

• 1 <= nums.length <= 5 * 104
• 1 <= nums[i] <= 107
• nums 按 升序 排列，其中所有元素 互不相同 。
• 1 <= k <= 108

 

进阶：你可以设计一个对数时间复杂度（即，O(log(n))）的解决方案吗？

解法

方法一：二分查找

我们设计一个函数 $missing(i)$，表示 $nums[i]$ 与 $nums[0]$ 之间缺失的元素个数。那么 $missing(i)$ 就等于 $nums[i] - nums[0] - i$。我们可以通过二分查找找到最小的 $i$，使得 $missing(i) \geq k$，那么 $nums[i - 1] + k - missing(i - 1)$ 就是第 $k$ 个缺失的元素。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 $nums$ 的长度。

class Solution:
  def missingElement(self, nums: List[int], k: int) -> int:
    def missing(i: int) -> int:
      return nums[i] - nums[0] - i

    n = len(nums)
    if k > missing(n - 1):
      return nums[n - 1] + k - missing(n - 1)
    l, r = 0, n - 1
    while l < r:
      mid = (l + r) >> 1
      if missing(mid) >= k:
        r = mid
      else:
        l = mid + 1
    return nums[l - 1] + k - missing(l - 1)

class Solution {
  public int missingElement(int[] nums, int k) {
    int n = nums.length;
    if (k > missing(nums, n - 1)) {
      return nums[n - 1] + k - missing(nums, n - 1);
    }
    int l = 0, r = n - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (missing(nums, mid) >= k) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return nums[l - 1] + k - missing(nums, l - 1);
  }

  private int missing(int[] nums, int i) {
    return nums[i] - nums[0] - i;
  }
}

class Solution {
public:
  int missingElement(vector<int>& nums, int k) {
    auto missing = [&](int i) {
      return nums[i] - nums[0] - i;
    };
    int n = nums.size();
    if (k > missing(n - 1)) {
      return nums[n - 1] + k - missing(n - 1);
    }
    int l = 0, r = n - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (missing(mid) >= k) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return nums[l - 1] + k - missing(l - 1);
  }
};

func missingElement(nums []int, k int) int {
  missing := func(i int) int {
    return nums[i] - nums[0] - i
  }
  n := len(nums)
  if k > missing(n-1) {
    return nums[n-1] + k - missing(n-1)
  }
  l, r := 0, n-1
  for l < r {
    mid := (l + r) >> 1
    if missing(mid) >= k {
      r = mid
    } else {
      l = mid + 1
    }
  }
  return nums[l-1] + k - missing(l-1)
}