leetcode：1060. 有序数组中的缺失元素（会员题）

题目

给出一个 有序数组 A，数组中的每个数字都是 独一无二的，找出从数组最左边开始的第 K 个缺失数字。

示例：

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

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

解答 & 代码

解法一：遍历

#include <iostream>
#include <vector>
using namespace std;

/* 找出从数组 nums 最左边开始的第 k 个缺失数字*/
int missingElement(vector<int> nums, int k)
{
    int len = nums.size();
    int cnt = 0;                    // 缺失数字个数
    for(int i = 1; i < len; ++i)    // 遍历数组
    {
        // 如果到当前元素 nums[i] 为止的缺失数字个数大于等于 k
        if(cnt + nums[i] - nums[i - 1] - 1 >= k)
            return nums[i - 1] + k - cnt;    // 则返回第 k 个缺失数字
        cnt += nums[i] - nums[i - 1] - 1;    // 更新缺失数字个数
    }
    // 缺失的数字大于数组最后一个数，返回缺失的数字
    return nums[len - 1] + k - cnt;
}

int main()
{
    vector<int> nums = {4, 7, 9, 10};
    int k = 1;  // result = 5
    cout << missingElement(nums, k);
    return 0;
}

复杂度分析：设数组长为 n

  • 时间复杂度 O(n)：遍历数组
  • 空间复杂度 O(1)：

解法二：二分查找

#include <iostream>
#include <vector>
using namespace std;

int missingElement(vector<int> nums, int k)
{
    int len = nums.size();
    int left = 0;
    int right = len - 1;
    while(left <= right)
    {
        int mid = left + (right - left) / 2;
        int cnt = nums[mid] - nums[0] - mid;    // mid 之前缺失的数字个数
        if(cnt >= k)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return nums[right] + k - (nums[right] - nums[0] - right);
}

int main()
{
    vector<int> nums = {4, 7, 9, 10};
    int k = 1;  // result = 5
    cout << missingElement(nums, k);
    return 0;
}

复杂度分析：设数组长为 n

  • 时间复杂度 O(log n)：二分查找
  • 空间复杂度 O(1)：