這是一個作業問題。他們說這需要O(logN + logM)在哪里N，M是數組的長度。讓我們命名的數組a和b。顯然，我們可以忽略所有a[i]和b[i]其中i>?。首先，我們比較a[k/2]和b[k/2]。讓b[k/2]> a[k/2]。因此，我們也可以丟棄所有b[i]，其中i> k / 2。現在我們有了a[i]i <k和all> b[i]i <k / 2的全部，以找到答案。你下一步怎么做？
3 回答
子衿沉夜
TA貢獻1828條經驗 獲得超3個贊
您已掌握，繼續前進！并注意索引...
為了簡化一點，我將假設N和M> k，因此這里的復雜度為O（log k），即O（log N + log M）。
偽代碼：
i = k/2
j = k - i
step = k/4
while step > 0
if a[i-1] > b[j-1]
i -= step
j += step
else
i += step
j -= step
step /= 2
if a[i-1] > b[j-1]
return a[i-1]
else
return b[j-1]
為了演示，您可以使用循環不變i + j = k，但我不會做所有作業：)
湖上湖
TA貢獻2003條經驗 獲得超2個贊
自問這個問題以來已經過去了一年多，我希望我不回答您的作業。這是尾部遞歸解決方案，將花費log（len（a）+ len（b））時間。
假設：輸入正確。即k在[0，len（a）+ len（b）]范圍內
基本案例：
如果數組之一的長度為0，則答案為第二個數組的第k個元素。
減少步驟：
如果中指a+中指b小于k
如果的中間元素a大于的中間元素b，我們可以忽略的前一半b，進行調整k。
否則忽略上半年的a調整k。
否則，如果k小于和的中間索引之a和b：
如果中的元素a大于中的元素b，我們可以放心地忽略中的后一半a
否則我們可以忽略 b
碼：
def kthlargest(arr1, arr2, k):
if len(arr1) == 0:
return arr2[k]
elif len(arr2) == 0:
return arr1[k]
mida1 = len(arr1)/2
mida2 = len(arr2)/2
if mida1+mida2<k:
if arr1[mida1]>arr2[mida2]:
return kthlargest(arr1, arr2[mida2+1:], k-mida2-1)
else:
return kthlargest(arr1[mida1+1:], arr2, k-mida1-1)
else:
if arr1[mida1]>arr2[mida2]:
return kthlargest(arr1[:mida1], arr2, k)
else:
return kthlargest(arr1, arr2[:mida2], k)
請注意，我的解決方案是在每次調用中創建較小數組的新副本，只需在原始數組上傳遞開始和結束索引即可輕松消除這種情況。
添加回答
舉報
0/150
提交
取消