.jpeg)
Given a sorted array A of unique numbers, find the K-th missing number starting from the leftmost number of the array.
Example 1
1
2
3
4
| Input: A = [4,7,9,10], K = 1
Output: 5
Explanation:
The first missing number is 5.
|
Example 2:
1
2
3
4
| 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:
1
2
3
4
| 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.
|
找第K個遺失值，由於需要比n更快的搜尋方式，自然會想到二分搜尋的O(log n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| T:O(logn), S:O(1)
from typing import List
class Solution:
def missingElement(self, nums: List[int], k: int) -> int:
left, right=0, len(nums)-1 # index 0-3
while left<= right:
mid=(left+right)//2 # floor
missing_nums=nums[mid]-nums[0]-mid # 知道少幾個值
if missing_nums<k:
left= mid+1
else:
right= mid-1
return nums[0]+left+k-1
print(Solution().missingElement([4,7,9,10],1))
|