quickSelect在Python中的HW

我已經給出了quickSelect算法的以下僞代碼。當我將quickSelect方法稱爲'k'時，我對一些事情有點困惑。另外，因爲我需要在方法的開頭聲明count = 0，所以在quickSelect的遞歸調用中它總是會回到0，這不是我需要發生的事情感謝您的幫助，我已將Pseudo代碼以及我的代碼如下;quickSelect在Python中的HW

Function quickSelect(aList, k): 
If aList is not empty: 
    pivot <- Choose the element at position (len(alist)//2) 
    smallerList <- All elements of aList smaller than pivot 
    largerList <- All elements of aList larger than pivot 
    count <- the number of occurences of pivot value in aList 
    m <- the size of smallerList 
    if k >= m and k < m + count then: 
     return pivot 
    if m > k: 
     return quickSelect(smallerList,k) 
    else: 
     return quickSelect(largerlist, k-m-count)

這是我想出來的：

def quickSelect(aList, k): 
    pivot = aList[len(aList)//2] 
    smallerList = aList[:pivot] 
    largerList = aList[pivot:] 
    m = len(smallerList) 
    count = 0 

    for i in aList: 
     if i == pivot: 
     count = count + 1 

    if k >= m and k < m + count: 
     return pivot 
    if m > k: 
     return quickSelect(smallerList, k) 
    else: 
     return quickSelect(largerList, k-m-count)

來源

2012-10-16 Talen Kylon

你的代碼不工作的方式是什麼？（你能否提供一些與期望輸出一起的輸出示例？） –

首先，你必須smallerList和largerList採取基於其索引樞軸兩側的內容，而不是他們的價值。數據透視應該用索引的內容來劃分數字，而不是索引的位置（例如，如果索引是5，那麼所有小於數字5的條目都需要分配給smallerList，並且需要將所有更大的數字分配給largerList是大於5

這可以通過一個簡單的做for循環：

if len(aList)!=0: 
pivot=aList[(len(aList)//2)] 
smallerList = [] 
for i in aList: 
    if i<pivot: 
     smallerList.append(i) 
largerList=[] 
for i in aList: 
    if i>pivot: 
     largerList.append(i) 
m=len(smallerList) 
count=len(aList)-len(smallerList)-len(largerList)

smallerList和largerList將/不/包括樞軸，因此計數（發生倍樞軸的數目）將是主列表的長度減去較小和較大列表的組合長度。

現在，如果k（第k個最小數字）大於或等於m，則較小列表的長度AND k小於較小列表的長度+數據透視的計數，則需要返回透視，因爲它是您尋找的第k個最小的數字。

if k >= m and k<m + count: 
    return pivot

或者，如果小名單的長度大於k，執行快速再次選擇只使用smallerList，而不是完整的列表。

elif m > k: 
    return quickSelect(smallerList,k)

否則，運行快速使用較大的列表，而不是完整的列表中再次選擇，並查找的k - 小名單的長度 - 樞軸

else: 
    return quickSelect(largerList, k - m - count)

的計數此函數會自己過來，（比線性排序快得多），並且會讓你回到樞軸一旦滿足。這種情況下的樞軸點將是中位數。

希望這會有所幫助！

來源

2012-10-17 15:33:09 mttalxndrgrrtt

quickSelect在Python中的HW

回答

相關問題