查找單峯數組中的第k個元素

給定一個n個不同元素的單峯數組A（意味着它的條目按遞增順序排列直到其最大元素，之後其元素的遞減順序），則整數p （即增加的第一部分的長度）和k（第k個最小元素）給出算法以計算在O（log n）時間中運行的第k個最小元素的值。查找單峯數組中的第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)

來源

2013-03-25 KienMe

你試過了什麼？ – noMAD 2013-03-25 21:42:29

不應該是3？ – biziclop 2013-03-25 21:42:29

隨着第一部分的增加和其餘的減少，你基本上有兩個排序的數組。查看[this]（http://stackoverflow.com/a/12555973/1011995）或[this]（http://stackoverflow.com/questions/4607945/how-to-find-the-kth-smallest-element在兩個排序的數組中）或其他很多問題。 – 2013-03-25 22:00:09

對於初學者來說再看看你的索引。你開始用：

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-27 12:08:03

好點，這部分代碼「arr1 [len（arr1）-k-1]」必須是arr1 [k] – KienMe 2013-03-27 18:50:43

如果你的索引從1開始，那麼你還需要看一下這一行的索引： return arr2 [len（arr2）-k-1] – 2013-03-28 13:17:41

查找單峯數組中的第k個元素

回答

相關問題