gpt4 book ai didi

algorithm - 在单峰数组中找到第 k 个元素

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:02:54 24 4
gpt4 key购买 nike

给定一个包含 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)

最佳答案

对于初学者来说,再看看你的索引。你开始于:

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

但是可以肯定的是,如果 arr1 是升序的,而 arr2 是降序的,则不会在同一位置找到第 k 个最小元素。

关于algorithm - 在单峰数组中找到第 k 个元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15625316/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com