發現排列第k個最大的元素袋

我們收集了一個Comparable s在一個袋子裏，必須找到第k第一大元素。我將集合複製到HashSet以刪除重複項，然後將HashSet轉換爲要排序的數組，然後訪問第k個元素。代碼編譯，但測試失敗，我無法弄清楚什麼是錯的。有任何想法嗎？發現排列第k個最大的元素袋

public E kth(int k) { 
    uniqueSet(); 
    Object[] uniqueArr = hashSet.toArray(); 
    startQuick(uniqueArr); 
    return (E) uniqueArr[k - 1]; 
} 

private void startQuick(Object[] uniqueArr) { 
    int i = 0, j = uniqueArr.length; 
    quickSort(uniqueArr, 0, j); 
} 

private void quickSort(Object[] uniqueArr, int i, int j) { 
    int index = partition(uniqueArr, i, j); 
    if (i < index - 1) { 
     quickSort(rankBagArr, index - 1, j); 
    } 
    if (index < j) { 
     quickSort(rankBagArr, i, index - 1); 
    } 
} 

private int partition(Object[] uniqueArr, int i, int j) { 
    E tmp; 
    E pivot = (E) rankBagArr[(i + j)/2]; 

    while (i <= j) { 
     while (rankBagArr[i].compareTo(pivot) < 0) { 
      i++; 
     } 
     while (rankBagArr[j].compareTo(pivot) > 0) { 
      j--; 
     } 

     if (i <= j) { 
      tmp = (E) rankBagArr[i]; 
      rankBagArr[i] = rankBagArr[j]; 
      rankBagArr[j] = tmp; 
      i++; 
      j--; 
     } 
    } 
    return i; 
}

來源

2009-09-09 learner01

什麼是rankBagArr？這是一個錯字，應該是唯一的嗎？ – 2009-09-09 08:47:59

一開始這部分是高度懷疑：

if (i < index - 1) 
     quickSort(rankBagArr, index-1 ,j); 
    if (index < j) 
     quickSort(rankBagArr, i, index-1);

你不是說：

if (i < index - 1) 
     quickSort(rankBagArr, i, index-1); 
    if (index + 1 < j) 
     quickSort(rankBagArr, index + 1, j);

？

我不熟悉你的分區方法，所以我不知道這是否正確。我認爲我明白了，它在檢查上看起來沒問題，但是如果沒有仔細研究的話，很容易發現難以查看的錯誤。

這裏是我最近在C＃中編寫的分區方法 - 如果需要，您應該可以很容易地將其轉換爲Java。

private static int Partition<T>(T[] array, int left, int right, 
    IComparer<T> comparer) { 
    // Pivot on the rightmost element to avoid an extra swap 
    T pivotValue = array[right]; 
    int storeIndex = left; 
    for (int i = left; i < right; i++) { 
    if (comparer.Compare(array[i], pivotValue) < 0) { 
     Swap(array, i, storeIndex); 
     storeIndex++; 
    } 
    } 
    Swap(array, right, storeIndex); 
    return storeIndex; 
} 

static void Swap<T>(T[] array, int x, int y) { 
    T tmp = array[x]; 
    array[x] = array[y]; 
    array[y] = tmp; 
}

不是僅僅使用Arrays.sort的任何理由？

來源

2009-09-09 08:44:27

也許你可以有少了幾分操作的（並提高性能），並糾正您所看到的默認...

用List（ArrayList的）開始，你可以要求對它進行排序（使用比較器和Collections.sort(list)）。然後，您可以循環下來：

記憶的最後一個元素
如果你找到新的元素不等於，遞增計數器
當您的計數器達到k值，當前元素是你的目標

來源

2009-09-09 08:46:36 KLE

如果你想通過排序，然後

使用排序從API方法（Arrays.sort解決問題或Collections.sort）。重新發明輪子毫無意義。
對你的收藏的內容進行一次排序，而不是每次查找第k個元素。

快速排序分區適用於在不排序整個集合的情況下查找第k個元素 - 如果最小範圍大於k，那麼您經常使用分區降低範圍，如果它小於k，到更高的範圍並尋找（k範圍下限）第 - 個元素。它比分類整個集合要複雜得多。您可以閱讀更多關於它的信息here

無論如何，您的方法的參數名爲uniqueArr，但您在rankBagArr上執行的一些操作。這是一個錯字嗎？您的代碼中沒有rankBagArr的定義。

來源

2009-09-09 10:43:55

發現排列第k個最大的元素袋

回答

相關問題