描述
给出一个有序数组 A，数组中的每个数字都是 独一无二的，找出从数组最左边开始的第 K 个缺失数字。
示例 1：
输入：A = [4,7,9,10], K = 1
输出：5
解释：
第一个缺失数字为 5 。
示例 2：
输入：A = [4,7,9,10], K = 3
输出：8
解释：
缺失数字有 [5,6,8,…]，因此第三个缺失数字为 8 。
示例 3：
输入：A = [1,2,4], K = 3
输出：6
解释：
缺失数字有 [3,5,6,7,…]，因此第三个缺失数字为 6 。
提示:
- 1 <= A.length <= 50000
- 1 <= A[i] <= 1e7
- 1 <= K <= 1e8
解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| public class Solution {
public int missingElement(int[] nums, int k) {
int start = nums[0];
for (int i = 1; i < nums.length; i++) {
int tmp = nums[i];
if (tmp == start + 1) {
start++;
} else {
int minusVal = tmp - start -1;
if (minusVal >= k)
return start + k;
else {
k -= minusVal;
start = tmp;
}
}
}
return start + k;
}
public static void main(String[] args) {
var q = new q2019_04_21比赛1();
var res1 = q.missingElement(new int[]{4, 7, 9, 10}, 1);
System.out.println(res1 == 5);
var res2 = q.missingElement(new int[]{4,7,9,10}, 3);
System.out.println(res2 == 8);
var res3 = q.missingElement(new int[]{1,2,4}, 3);
System.out.println(res3 == 6);
}
}
|
注意点:
主要判断数组中两个元素中间缺几个数,如果大于等于k,则直接返回结果,否则进入下一个循环判断