Leaky Cauldron
0%

Missing Element in Sorted Array

Posted on Edited on

题目(LeetCode #1060)

Given a sorted array A of unique numbers, find the K-th missing number starting from the leftmost number of the array.

Example 1:

Input: A = [4,7,9,10], K = 1
Output: 5
Explanation:
The first missing number is 5.

Example 2:

Input: A = [4,7,9,10], K = 3
Output: 8
Explanation:
The missing numbers are [5,6,8,…], hence the third missing number is 8.

Example 3:

Input: A = [1,2,4], K = 3
Output: 6
Explanation:
The missing numbers are [3,5,6,7,…], hence the third missing number is 6.

Note:

  1. 1 <= A.length <= 50000
  2. 1 <= A[i] <= 1e7
  3. 1 <= K <= 1e8

题解

方法一

逐个计算数组中的元素：

  1. k 大于等于数组中最后一个数时, 除了数组中的数全部缺失, 故相当于求以 nums[0] 开始的第 k + n 项；
  2. 若 k 小于数组中最后一个数，则逐个计算数组元素，若元素存在则数组指针右移，若遇到缺失元素则 k--。最终 num + k 即为第 k 个缺失元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int missingElement(int[] nums, int k) {
        if (nums == null || nums.length == 0) return k;

        int n = nums.length;
        if (k >= nums[n - 1]) return k + nums[0] + n - 1;

        int num = nums[0];
        int idx = 1;
        while (idx < n && k > 0) {
            if (++num == nums[idx]) idx++;
            else k--;
        }

        return num + k;
    }
}

方法二

通过二分查找，找到第 k 个缺失数字之前的值在 nums 中的索引。最终结果为 nums[0] + x + k，其中 x 为第 k 个缺失的数字前在 nums 数组中已经存在的元素个数。

使用二分法的一个关键问题在于如何缩小查找范围。若第 k 个缺失的数字在 [l, m] 之间，那么可知 nums[m] >= nums[0] + k + m。由此可反推判断条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int missingElement(int[] nums, int k) {
        if (nums == null || nums.length == 0) return k;

        int l = 0, r = nums.length - 1;
        while (l < r) {
            int m = l + (r - l + 1) / 2;
            if (nums[m] >= nums[0] + k + m) r = m - 1;
            else l = m;
        }

        return nums[0] + l + k;
    }
}