4

n個の異なる要素のユニモーダル配列Aが与えられた場合（そのエントリは最大要素まで昇順であり、その後は要素が降順であることを意味します）、整数p（つまり、増加する最初の部分の長さ）およびk (k 番目の最小要素) O(log n) 時間で実行される k 番目の最小要素の値を計算するアルゴリズムを与えてください。

例：

A= {1,23,50,30,20,2} 
p= 2
k=3

答え: 20

編集

私はこれを試しました：

def ksmallest(arr1, arr2, k):
if len(arr1) == 0:
    return arr2[len(arr2)-k-1]
elif len(arr2) == 0:
    return arr1[k]
mida1 = (int)(len(arr1)/2)
mida2 = (int)((len(arr2)-1)/2)
if mida1+mida2<k:
    if arr1[mida1]>arr2[mida2]:
        return ksmallest(arr1, arr2[:mida2], k-(len(arr2)-mida2))
    else:
        return ksmallest(arr1[mida1+1:], arr2, k-mida1-1)
else:
    if arr1[mida1]>arr2[mida2]:
        return ksmallest(arr1[:mida1], arr2, k)
    else:
        return ksmallest(arr1, arr2[mida2+1:], k)
4

1 に答える 1

0

手始めに、インデックスをもう一度見てください。次から始めます。

if len(arr1) == 0:
    return arr2[len(arr2)-k-1]
elif len(arr2) == 0:
    return arr1[len(arr1)-k-1]

しかし、arr1 が昇順で、arr2 が降順の場合、k 番目の最小要素は同じ場所には見つかりません。

于 2013-03-27T12:08:03.763 に答える