py党求助median of medians, 3RE+2MLE

P1923 【深基9.例4】求第 k 小的数

Sapnap_ @ 2022-08-13 10:51:42

最近在学算法,学到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]))

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]这玩意慎用. 切片是复制一份


|