LeetCode 1539. Kth Missing Positive Number
一樣是學習計畫中的,不過這題就沒什麼人按爛,兩題概念明明差不多,真奇怪。
題目Permalink
輸入陣列arr以及整數k。從1開始數,求第k個沒arr中出現的數字是多少。
解法Permalink
一樣暴力貪心,n紀錄當前數字,i紀錄arr中輪到第幾個。如果n不等於arr[i]才把k遞減,重複到k沒有為止。
class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
n=0
i=0
N=len(arr)
while k:
n+=1
if i<N and arr[i]==n:
i+=1
else:
k-=1
return n
改成set更清楚。
class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
s=set(arr)
n=0
while k:
n+=1
if n not in s:
k-=1
return n
重點的二分搜。
這公式是難想了一點,說是medium程度也不為過。
在arr[i]以前且沒在arr中出現的數字有arr[i]-i-1個。
例如:
arr = [2,3,4,7,11], k = 5
i=0, arr[0]=2, 在2以前有2-0-1個不在arr的數字
i=1, arr[3]=3, 在3以前有3-1-1個不在arr的數字
… i=4, arr[4]=11, 在11以前有11-4-1個不在arr的數字
下界為0,是arr中的第一個位置,上界為N,用來搜第mid個位置。如果上界用N-1的話,arr長度剛好為1時就會出錯。
如果沒出現的數字不足k,更新下界為mid+1,否則更新上界為mid。最後停止時,代表正好有lo個數出現在arr中,所以答案就是lo+k。
class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
lo=0
hi=len(arr)
while lo<hi:
mid=(lo+hi)//2
if arr[mid]-mid-1<k:
lo=mid+1
else:
hi=mid
return lo+k