0

私はPythonが初めてで、コードを書く練習をしていますが、いくつかの問題があります。

K 個の最大要素を抽出できるQuickSelectに基づくアルゴリズムを実装しようとしています。

そのため、アルゴリズムを実装し、QuickSelectそれを使用して配列 A の K 番目に大きい要素を見つける前に、関数を使用して配列 A をスキャンし、で見つかった K 番目の要素以上のK 要素k_largest_quickselect(A, 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 に答える