Sapnap_ @ 2022-08-13 10:51:42
最近在学算法,学到Median of Medians (快速选择算法的严格
本人萌新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]))
by Sapnap_ @ 2022-08-13 10:52:36
有可能是没有考虑到重复元素?但那应该是wa而不是re啊...
by Sapnap_ @ 2022-08-13 11:05:18
样例过了,把n[0]调小(5以下)用midofmid跑样例也过了
by okok8260 @ 2022-09-16 16:28:16
别的先不说,A[j:j + 5]
这玩意慎用. 切片是复制一份