LeetCode [1060] Missing Element in Sorted Array

1060. Missing Element in Sorted Array

Medium

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 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

class Solution { public int missingElement(int[] nums, int k) { int n = nums.length; int totalMissing = nums[n-1]-nums[0]-(n-1); if(k>totalMissing) return nums[n-1]+(k-totalMissing); //the target number must in [nums[0], nums[n-1]] //need to find the number nums[i] such that miss(0..i)<k & miss(0..i+1)>=k //the target number nums[i]+(k-miss(0..i)) //i must not be n-1; otherwise we would have k>totalMissing which is covered by the above conner condition //let x be missing(0..i) and y be missing(0..i+1) int l = 0, r = n-2; while(l<=r){ int m = (l+r)/2; int x = nums[m]-nums[l] - (m-l); int y = nums[m+1]-nums[l] - (m+1-l); if(x<k && y>=k){ return nums[m]+k-x; }else if(x>=k){ r = m-1; }else{//x<k & y<k l = m+1; k-=y; } } return -1; } }