查找单峰数组中的第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个元素

回答

相关问题