[Leetcode 1060] Missing Element in Sorted Array

原题说明

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

解题思路

显然暴力破解不是我们想要的方法。既然暴力破解的时间复杂度是O(N），那我们需要比这更优的解，一般只有O(logN)了。这样我们自然想到用binary search。
我们可以进行binary search。具体到这道题，我们按每个index对应的对应的missing elements的数量进行二分。如果大于K，则我们要求的第K个element一定在这个index的左边，小于K则一定在右边。找到这个转换点的index，就能通过计算得出想要的第k个missing element。

示例代码 (cpp)

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int N = nums.size() - 1;
        int left = 0, right = N;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int missingcount = missing(nums, mid);
            if (missingcount < k) {
                left = mid;
            }
            else {
                right = mid;
            }
        }
        return missing(nums, right) < k ? nums[right] + k - missing(nums, right) : nums[left] + k - missing(nums, left);
    }
    
    int missing(vector<int>& nums, int index) {
        return nums[index] - nums[0] - index;
    }
};

示例代码 (java)

class Solution {
    public int missingElement(int[] nums, int k) {
        int n = nums.length;
        int l = 0;
        int h = n - 1;
        int missingNum = nums[n - 1] - nums[0] + 1 - n;
        
        if (missingNum < k) {
            return nums[n - 1] + k - missingNum;
        }
        
        while (l < h - 1) {
            int m = l + (h - l) / 2;
            int missing = nums[m] - nums[l] - (m - l);
            
            if (missing >= k) {
			    // when the number is larger than k, then the index won't be located in (m, h]
                h = m;
            } else {
			    // when the number is smaller than k, then the index won't be located in [l, m), update k -= missing
                k -= missing;
                l = m;
            }
        }
        
        return nums[l] + k;
    }
}

示例代码 (python)

class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:
        if not nums or k == 0:
            return 0
        
        diff = nums[-1] - nums[0] + 1 # complete length
        missing = diff - len(nums) # complete length - real length
        if k > missing: # if k is larger than the number of mssing words in sequence
            return nums[-1] + k - missing
        
        left, right = 0, len(nums) - 1
        while left + 1 < right:
            mid = (left + right) // 2
            missing = nums[mid] - nums[left] - (mid - left)
            if missing < k:
                left = mid
                k -= missing # KEY: move left forward, we need to minus the missing words of this range
            else:
                right = mid
                
        return nums[left] + k # k should be between left and right index in the end

复杂度分析

时间复杂度: O(logN)
空间复杂度: O(1)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！