最近在学算法,学到Median of Medians (快速选择算法的严格 O(n) 版本,将数组分成好几个5个一组的,每一组里选取中位数,再找中位数的中位数,可以参考这篇题解)
本人萌新py党(因此c++题解好像不适用),决定尝试用这个算法A这道题,结果...3RE+2MLE
哪位帮我看一下哪里有问题,不许无意义回复,谢谢
def midofmid(A, i):
sublists = [A[j:j + 5] for j in range(0, len(A), 5)]
medians = [sorted(group)[len(group) / 2] for group in sublists]
if len(medians) <= 5:
piv = sorted(medians)[len(medians) / 2]
else:
piv = midofmid(medians, len(medians) / 2)
less = [j for j in A if j <= piv]
greater = [j for j in A if j > piv]
l = len(less)
if i < l:
return midofmid(less, i)
elif i > l:
return midofmid(greater, i - l - 1)
else:
return piv
n = list(map(int, input().split()))
arr=list(map(int,input().split()))
if n[0]<=140:
srtd = sorted(arr)
print(srtd[n[1]])
else:
print(midofmid(arr,n[1]))