0

我是 Python 新手，我正在练习编写代码，但我遇到了一些麻烦。

我正在尝试实现一种基于QuickSelect的算法，在该算法中可以提取K 个最大元素。

所以，在我实现QuickSelect算法并使用它找到数组 A 中的第 K 个最大元素之前。然​​后使用函数k_largest_quickselect(A, K)我扫描数组 A 以收集大于或等于找到的第 K 个元素的 K 个元素，最后QuickSelect，对收集到的元素进行排序。

这是我的实现代码：

def partition(A, left, right): 
    pivot = random.choice(A)  # pick a random number as pivot
    i = left - 1
    for j in range(left, right): 
        if A[j] <= pivot: 
            i = i+1 
            A[i], A[j] = A[j], A[i]
    A[i+1], A[right] = A[right], A[i+1] 
    return i+1

def QuickSelect(A, K, left, right): # Array, K-th element
    if left == right:
        return A[left]
    q = partition(A, left, right)
    i = q - left + 1
    if K == i:
        return A[i]
    if K < i:
        return QuickSelect(A, K, left, q - 1)
    else:
        return QuickSelect(A, K - i, q + 1, right)
    
def k_largest_quickselect(A, K):
    B = [i for i in A if i >= QuickSelect(A = A, K = K, left = 0, right = len(a)-1)] # elements >= the K-th element found with QuickSelect
    B.sort(reverse = True)
    return B

我试图测试算法

a = get_random_array(10, 10)
print("Array a = " + str(a))
print(sorted(a)[-3:])
print(sorted(k_largest_quickselect(a, 3))) # from array a select the 3 highest number

得到这个结果

Array a = [0, 3, 0, 6, 2, 5, 1, 8, 1, 9]
[6, 8, 9]
[2, 5, 6, 6, 9, 9]

如您所见，通过使用该函数，k_largest_quickselect(A = a, K = 3)我没有得到数组的 3 个最大元素。

拜托，你能帮我解决这个问题吗？非常感谢！

4

1 回答 1

0

这是算法的另一种方法：

def kSelect(a, k):
    largestElements = []
    
    for interation in range(0,k):
        largestElementInArray = max(a)
        largestElements.append(largestElementInArray)
        a.remove(largestElementInArray)

    return largestElements

不确定这是否是您想要实现的目标..？

于 2021-06-13T11:09:34.900 回答