給定一個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

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

+1

你試過了什么？ –

2013-03-25 21:42:29

+2

不應該是3？ –

2013-03-25 21:42:29

+8

隨著第一部分的增加和其余的減少，你基本上有兩個排序的數組。查看[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

總結

以上是生活随笔為你收集整理的单峰数组找最大元素C语言,查找单峰数组中的第k个元素的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。