py党求助median of medians, 3RE+2MLE
查看原帖
py党求助median of medians, 3RE+2MLE
440653
Sapnap_楼主2022/8/13 10:51

最近在学算法,学到Median of Medians (快速选择算法的严格 O(n)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]))
2022/8/13 10:51
加载中...