0

s のコレクションがComparableバッグに保持されており、kth 番目に大きい要素を見つける必要があります。コレクションを a にコピーして重複を削除し、 を配列にHashSet変換してソートし、その結果、 th 要素にアクセスしました。コードはコンパイルされますが、テストに失敗し、何が問題なのかわかりません。何か案は？HashSetk

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;
}
4

3 に答える 3

3

まず、この部分は非常に疑わしいです:

  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);

?

パーティショニングへのあなたのアプローチに慣れていないので、それが正しいかどうかはわかりません。私はそれを理解していると思います。検査では問題ないように見えますが、慎重に検討しないと見えにくいエラーを 1 つずつ簡単に見つけることができます。

最近 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-09T08:44:27.083 に答える
1

並べ替えで問題を解決したい場合は、

  1. API の並べ替えメソッド (Arrays.sort または Collections.sort) を使用します。車輪の再発明は無意味です。
  2. k 番目の要素を探すたびにではなく、コレクションのコンテンツを 1 回並べ替えます。

クイックソート パーティショニングは、コレクション全体をソートせずに k 番目の要素を見つけるのに適しています。最小範囲が k よりも大きい場合は分割し、下位の範囲にパーティションを繰り返し移動し、k よりも小さい場合は上位の範囲に移動して探します(k - 下位範囲のサイズ)-th 要素。コレクション全体をソートするよりも複雑です。詳細については、こちらをご覧ください。

とにかく、あなたのメソッドにはuniqueArrという名前のパラメーターがありますが、rankBagArrで実行する操作もあります。タイプミスですか？コードに rankBagArr の定義がありません。

于 2009-09-09T10:43:55.907 に答える
0

操作を少し減らして（そしてパフォーマンスを向上させて）、表示されているデフォルトを修正できますように...

List (ArrayList) から始めて、(コンパレータと を使用して) 並べ替えを要求できますCollections.sort(list)。次に、ループして次のことができます。

  • 最後の要素を覚える
  • 新しい要素が等しくないことがわかった場合は、カウンターをインクリメントします
  • カウンターが k 値に達すると、現在の要素がターゲットになります
于 2009-09-09T08:46:36.220 に答える