找到第k個最小元素

-1

我跟着本書中的算法解決了這個問題。當我打印結果時，它是不正確的。該算法是完全按照書中我的代碼找到第k個最小元素

import math 

def quickSelect(A, k): 
    m = A[math.floor(len(A)/2)] 
    L = [i for i in A if i < m] 
    E = [i for i in A if i == m] 
    G = [i for i in A if i > m] 
    print(L) 
    print(E) 
    print(G) 

    if k <= len(L): 
    return quickSelect(L, k) 
    elif k <= (len(E) + len(G)): 
    return m 
    else: 
    return quickSelect(G, k- len(L) - len(E)) 

result = quickSelect([7, 14, 10, 12, 2, 11, 29, 3, 4], 4) 

print(result)

來源

2017-11-11 Sam Thapa

什麼是您預期的結果？ – Gumboy

我覺得第4個最小的應該是7對吧？但是當我運行時我得到2 –

你在第二次迴歸elif時的情況是錯誤的。 –

這些語句：

L = [i for i in A if i < m]  # less than m 
E = [i for i in A if i == m]  # equal to m 
G = [i for i in A if i > m]  # greater than m

分區排列爲三個範圍：

| L1 L2 L3 L4 | E1 | G1 G2 G3 
|     |  | 
0     |  | 
       len(L) | 
          len(L) + len(E)

你的條件爲第二範圍，

elif k <= (len(L) + len(G)): 
    return m

是錯誤的。它應該是：

elif k <= (len(L) + len(E)): 
    return m

節點：不要使用浮點運算的，你可以計算m與Python的整數除法：m = A[len(A) // 2]

來源

2017-11-11 18:51:52

謝謝，我錯了。如此愚蠢的錯誤 –

找到第k個最小元素

回答

相關問題