题目描述
现有一个按 升序 排列的整数数组 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$ 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | 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);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | 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)
}
|