Python 快速选择不打印/返回透视

Question

这是快速选择的代码

def quickSelect(lst, k):
if len(lst) != 0:
    pivot = lst[(len(lst)) // 2]
    smallerList = []
    for i in lst:
        if i < pivot:
            smallerList.append(i)
    largerList = []
    for i in lst:
        if i > pivot:
            largerList.append(i)
    count = len(lst) - len(smallerList) - len(largerList)
    m = len(smallerList)
    if k >= m and k < m + count:
        return pivot
        print(pivot)
    elif m > k:
        return quickSelect(smallerList, k)
    else:
        return quickSelect(largerList, k-m-count)

我遇到的问题是它运行没有错误或任何东西，但是当它自己完成时，我希望它向 python shell 输出一些东西（在这种特定情况下是列表的中位数），但我什么也没得到。我在这里做错了什么吗？

至于我为 lst 和 k 输入的内容....

• lst = [70， 120， 170， 200]
• k = len（lst）//2

我也尝试过几个不同的k值，但无济于事

Answer 1

您可以使用列表推导式优化此算法。另外，我认为你不需要计数...

 def quickSelect(seq, k):
    # this part is the same as quick sort
    len_seq = len(seq)
    if len_seq < 2: return seq
    ipivot = len_seq // 2
    pivot = seq[ipivot]
    smallerList = [x for i,x in enumerate(seq) if x <= pivot and  i != ipivot]
    largerList = [x for i,x in enumerate(seq) if x > pivot and  i != ipivot]
    # here starts the different part
    m = len(smallerList)
    if k == m:
        return pivot
    elif k < m:
        return quickSelect(smallerList, k)
    else:
        return quickSelect(largerList, k-m-1)


if __name__ == '__main__':
    # Checking the Answer
    seq = [10, 60, 100, 50, 60, 75, 31, 50, 30, 20, 120, 170, 200]
    # we want the middle element
    k = len(seq) // 2
    # Note that this only work for odd arrays, since median in
    # even arrays is the mean of the two middle elements
    print(quickSelect(seq, k))
    import numpy
    print numpy.median(seq)

Answer 2

def quickSelect(lst, k):
    if len(lst) != 0:
        pivot = lst[(len(lst)) // 2]
        smallerList = []
        for i in lst:
            if i < pivot:
                smallerList.append(i)
        largerList = []
        for i in lst:
            if i > pivot:
                largerList.append(i)
        count = len(lst) - len(smallerList) - len(largerList)
        m = len(smallerList)
        if k >= m and k < m + count:
            return pivot
            print(pivot)
        elif m > k:
            return quickSelect(smallerList, k)
        else:
            return quickSelect(largerList, k-m-count)
lst = [70, 120, 170, 200]
k = len(lst) // 2
print(quickSelect(lst, k))

生产

>>> 170

我唯一纠正的是缩进。