中位數的Medians算法錯誤

我正在實現一個使用中位數樞軸方法的select-kth算法。具體來說，我遵循pseudocode listed here.。然而，我的代碼崩潰（下面討論的錯誤），我明白爲什麼它崩潰，但我不明白我能做些什麼。中位數的Medians算法錯誤

的錯誤

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 32017219 
at Selection.partition(Selection.java:173)

原因
在維基鏈接，該方法select將返回一個值如果left == right。但是，當從pivot的返回語句中調用相互遞歸時，這意味着它將返回值（而不是索引）返回給父項，並且父項將該值設置爲pivotIndex。

守則

public static int alg5(int[] a, int left, int right, int k) { 
    if (left == right) { 
     return a[left]; 
    } 

    while (true) { 
     int pivotIndex = pivot(a, left, right);   
     pivotIndex = partition(a, left, right, pivotIndex); 

     if (k == pivotIndex) { 
      return a[k]; 
     } else if (k < pivotIndex) { 
      right = pivotIndex - 1; 
     } else { 
      left = pivotIndex + 1; 
     } 

    } 
} 

public static int pivot(int[] a, int left, int right) { 
    for (int i = left; i <= right; i = i + 5) { 
     int subRight = i + 4; 
     if (subRight > right) { 
      subRight = right; 
     } 

     int median5 = partition5(a, i, subRight); 
     swap(a, median5, (int)(Math.floor(i/5))); 
    } 

    return alg5(a, left, (int)(left + Math.ceil((right - left)/5) - 1), ((right - left)/10)); 
} 

public static int partition5(int[] a, int left, int right) { 
    Arrays.sort(a); 

    return ((a.length - 1)/2); 
} 

public static int partition(int[] a, int left, int right, int pivotIndex) { 
    int pivotValue = a[pivotIndex]; 
    a = swap(a, pivotIndex, right); 
    int storeIndex = left; 

    for (int i = left; i <= right; i++) { 
     int aOfi = a[i]; 
     if (a[i] < pivotValue) { 
      swap(a, storeIndex, i); 
      storeIndex++; 
     } 
    } 

    swap(a, right, storeIndex); 

    return storeIndex; 
}

我完全理解爲什麼我代碼不工作，我只是不知道如何，因爲它看起來是什麼算法指定修復它。指針非常感謝！

來源

2015-05-25 kfriede

據我可以告訴這是一個維基錯誤，試圖返回'pivotIndex'而比'a [k]'還要比較你的結果和已經實現的k-means算法，比如'R'（或者可能是matlab？）。 – ShellFish

@ShellFish相同的錯誤，在Selection.partition中出界。 – kfriede

有相當多的錯誤：

方法pivot不應該修改陣列a。它應該爲未來partition找到一個關鍵點。一個骯髒的修復方法是致電pivot(a.clone(), left, right);。（你不應該這樣做，只是爲了給你一個想法。）
Math.ceil((right - left)/5)是一個整數除法。你應該將它們投射到花車上：Math.ceil(((float)(right - left))/5f)。
在partition5，你排序整個陣列a！您只需進行比較即可找到a[left]和a[right]之間的中位數索引。
在某些時候，你可能有right < left，所以alg5第一線，你應該寫if (left >= right)

來源

2015-05-26 21:53:38 dejvuth

＃4修復了崩潰，謝謝！我通過搜索實現了＃3，並實現了＃1和＃2，它們改變了輸出，但它仍然不是正確的答案。我很高興現在的崩潰已經消失，所以我可以只關注爲什麼它會給出錯誤的答案。再次感謝您的解決方案！ – kfriede

中位數的Medians算法錯誤

回答

相關問題