05 August 2008
给定一个按升序排序的整数数组 nums，它的所有元素都是唯一的，并且还给定一个整数 k，返回从数组最左边的数字开始的第 k 个缺失的数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:
Input: nums = [4,7,9,10], k = 1
Output: 5
Explanation: The first missing number is 5.
Example 2:
Input: nums = [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: nums = [1,2,4], k = 3
Output: 6
Explanation: The missing numbers are [3,5,6,7,...], hence the third missing number is 6.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int missingElement(int[] nums, int k) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
int numOfMissingAtMid = getNumOfMissing(nums, mid);
if (numOfMissingAtMid < k) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left - 1] + (k - getNumOfMissing(nums, left - 1));
}
// this method takes an index and returns how many nums are missing
// between 0 and index
private int getNumOfMissing(int[] nums, int index) {
return (nums[index] - nums[0] + 1) - (index + 1);
}
}