2017-11-11 152 views
-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) 
+1

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

+0

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

+0

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

回答

3

這些語句:

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]

+0

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