0

我尝试实现快速选择以在列表中找到第 m 个最小的数字。当我运行程序时，它有时会在同一个数组上返回正确的值，而有时会返回不正确的值。我做错了什么她是代码

def select_mth_smallest(A, m):
    pivot = np.random.choice(A)
    # split into 3 partitions
    A1 = [] 
    A2 = []
    A3 = []
    for item in A:
        if item < pivot:
            A1.append(item)
        if item > pivot:
            A3.append(item)
        else:
            A2.append(item)
    #find where m'th largest element is and recurse accordingly
    if len(A1) >= m:
        return select_mth_smallest(A1, m)
    elif (len(A1) + len(A2)) >= m:
        return pivot
    else:
        return select_mth_smallest(A3,m - (len(A1)+len(A2)))

这是算法失败的输入。

A = [1,2,3,4,5]

select_mth_smallest(A,5)

当我反复执行上述语句时，我交替得到 5（正确）和 4（不正确）。

让我特别困惑的一件事（我是 python 新手）是为什么我在使用相同的输入重复时得到不同的函数返回值。看起来相当零星..顺便说一句，我正在使用 Jupyter

4

1 回答 1

2

您正在将一些项目添加到多个分区。

    if item < pivot:
        A1.append(item)
    if item > pivot:
        A3.append(item)
    else:
        A2.append(item)

A1是小于主元的项目集。A3是大于枢轴的项目集。A2然而，是小于或等于主元的项目集，因为第二条if语句对所有项目执行，并且将执行一个或另一个分支。

if您需要一个带有elifandelse子句的单一语句。

    if item < pivot:
        A1.append(item)
    elif item > pivot:
        A3.append(item)
    else:
        A2.append(item)
于 2016-05-02T20:50:26.233 回答