LeetCode: Missing Element in Sorted Array

Posted on August 5, 2019July 26, 2020 by braindenny

Missing Element in Sorted Array

Similar Problems:

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 <= A.length <= 50000
1 <= A[i] <= 1e7
1 <= K <= 1e8

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/missing-element-in-sorted-array
// Basic Ideas: binary search
//   Evaluate the left half or the right half
// Complexity: Time O(log(n)), Space O(1)
func missingElement(nums []int, k int) int {
    totalMiss := (nums[len(nums)-1]-nums[0]+1)-len(nums)
    if totalMiss < k {
        return nums[len(nums)-1]+k-totalMiss
    }
    left, right := 0, len(nums)-1
    for left+1<right {
        mid := (right-left)/2+left
        cnt := (nums[mid]-nums[left])-(mid-left)
        if cnt >= k {
            // search left part
            right = mid
        } else {
            // search right part
            left = mid
            k -= cnt
        }
    }
    // left.right
    return nums[left]+k
}

Post Views: 0