0

我正在尝试编写最佳算法来选择列表中较大的第 i 个元素。例如，如果 array = [4,3,5,7] 并且我搜索第二个，该函数将返回 4。

我假设列表在这里只有不同的数字

这是问题所在：

该函数有时会返回 None。

这是我的代码（我认为第一个函数运行良好）。

from random import shuffle

def partition(array, leftend, rightend, pivot):
    """ I tested this one and it should work fine """
    i = leftend
    pivotindex = array.index(pivot)  # only works if all values in array unique
    array[pivotindex] = array[leftend]
    array[leftend] = pivot
    for j in range(leftend+1, rightend):
        if array[j] < pivot:
            temp = array[j]
            array[j] = array[i]
            array[i] = temp
            i += 1
    pivotindex = array.index(pivot)  # only works if all values in array unique
    leftendval = array[pivotindex]   # Take the value of the pivot
    array[pivotindex] = array[i]
    array[i] = leftendval
    return array

def RSelect(array, n, statistic_order):
    """ list * int * int
        statistic_order = the i th element i'm searching for """
    new_array = []                  # is used at the end of the function
    if n == 1:
        return array[0]
    array_temp = array              # Allows to have a shuffled list and
    shuffle(array_temp)
    pivot = array_temp[0]           # Allows to have a random pivot
    partition(array,0,n,pivot)
    j = array.index(pivot)


    if j == statistic_order:
        return pivot


    elif j > statistic_order:
        for k in range(0,j):
            new_array.append(array[k])
        RSelect(new_array,j,statistic_order)


    elif j < statistic_order:
        for k in range(j+1,n):
            new_array.append(array[k])
        RSelect(new_array,(n-j)-1,statistic_order-j)
4

2 回答 2

0

代码工作正常，但结果仍然从 0 开始。例如，如果 arr = [2,3,5,6] 并且我要求 RSelect(arr,4,2)，答案将是 5 而不是 3。我不知道为什么。

这是更新的代码：

from random import shuffle

def partition(array, leftend, rightend, pivot):
    i = leftend
    pivotindex = array.index(pivot)  # only works if all values in array unique
    array[pivotindex] = array[leftend]
    array[leftend] = pivot
    for j in range(leftend+1, rightend):
        if array[j] < pivot:
            temp = array[j]
            array[j] = array[i]
            array[i] = temp
            i += 1
    pivotindex = array.index(pivot)  # only works if all values in array unique
    leftendval = array[pivotindex]   # Take the value of the pivot
    array[pivotindex] = array[i]
    array[i] = leftendval


def RSelect(array, n, statistic_order):
    """ list * int * int
        statistic_order = the i th element i'm searching for """
    if n == 1:
        return array[0]

    array_temp = array              # Allows to have a shuffled list
    shuffle(array_temp)
    pivot = array_temp[0]           # Allows to have a random pivot
    partition(array,0,n,pivot)
    j = array.index(pivot)


    if j == statistic_order:
        return pivot


    elif j > statistic_order:
        return RSelect(array[0:j],j,statistic_order)


    elif j < statistic_order:
        return RSelect(array[j+1:n],(n-j)-1,statistic_order-j-1)
于 2018-05-27T16:40:57.787 回答
0

好吧，有几件事是错误的：

  • 在任何情况下，您都需要以递归方法返回结果！
  • 当 j < statistic_order 时，您递归地处理数组的右侧部分，并丢弃 j+1 个数字，而不是 j。请记住，python 中的索引从 0 开始，而不是 1 ！

我还更改了一些东西，例如无用的参数，或者可以用切片编写的 for 循环。

这是最终代码，请检查更改以确保您理解它。

R选择：

def RSelect(array, statistic_order):
    """ list * int * int
    statistic_order = the i th element i'm searching for """
    n = len(array)
    if n == 1:
        return array[0]
    array_temp = array              # Allows to have a shuffled list and
    shuffle(array_temp)
    pivot = array_temp[0]           # Allows to have a random pivot
    array = partition(array,0,n,pivot)  # Changes here, does not impact the result, but for readability
    j = array.index(pivot)

    # print(array, j, statistic_order, end = '\t')
    if j == statistic_order:
        return pivot

    elif j > statistic_order:
        assert j > 0
        # print((array[0:j]), pivot)
        return RSelect(array[0:j],statistic_order)  # Changes here : return

    elif j < statistic_order:
        assert j+1 < n
        # print(pivot, (array[j+1:n]))
        return RSelect(array[j+1:n],statistic_order-j-1)  # Changes here : return, -j-1

主要的 ：

if __name__ == "__main__":
    from sys import argv
    if len(argv) > 1:
       n = int(argv[1])
    arr = [2, 1, 3, 5, 4]
    print(RSelect(arr[:], n))

为此目的，它也在 O(n) 中存在另一种算法：请参阅此

编辑：错别字更正和关于复杂性的更正

于 2018-05-23T13:37:42.053 回答