1

宿題の問題として、クイックソート スタイルのパーティショニングを使用して、配列内で k 番目に小さい数値を見つける Java メソッドを作成する必要があります。partition() メソッドが与えられたので、k 番目に小さい数を取得するメソッドを作成することになっています。

問題は、ピボットが常に配列範囲の右端の要素であることを要求します。

私は次のものを与えられました：

public int partition(int left, int right, long pivot) {
    int leftPtr = left - 1;
    int rightPtr = right + 1;
    while (true) {
        while (leftPtr < right && array[++leftPtr] < pivot); 
        while (rightPtr > left && array[--rightPtr] > pivot);

        if (leftPtr >= rightPtr)
            break;
        else
            swap(leftPtr, rightPtr);
    }
    return leftPtr;
}

そして、ウィキペディアの疑似コードに基づいてこのメソッドを作成しました。

public int kthSmallest(int left, int right, int k){
    if(left >= right){
        return array[left];
    }

    int pivotNewIndex = partition(left, right, array[right]);

    int pivotDist = pivotNewIndex - left - 1;

    if(pivotDist == k){
        return array[pivotNewIndex];
    } else if(k < pivotNewIndex){
        return kthSmallest(k, left, pivotNewIndex - 1);
    } else{
        return kthSmallest(k - pivotDist, pivotNewIndex + 1, right);
    }
}

しかし、kthSmallest()ランダムに生成された整数の配列で呼び出すと、約半分の時間で間違った値が返されます。例えば：

array: [45, 60, 24, 82, 87, 79, 16, 32, 59, 83, 20, 2, 1, 
         50, 11, 79, 72, 32, 0, 48, 69, 74, 22, 6, 96]
expected result when k=4: 11
actual result when k=4: 87

私は何を間違っていますか？

4

3 に答える 3

1

再帰呼び出しの引数リストの順序が間違っています。見ているサブ配列内の位置は、最初の引数ではなく、3 番目の引数である必要があります。

于 2012-05-10T03:46:16.750 に答える
1

ウィキペディアの疑似コードと比較して、kthSmallest の再帰呼び出しをよく見てください。k インデックス引数はどこに相対的ですか?

于 2012-05-10T03:37:51.893 に答える
0

これが効率的な解決策です（Java実装を使用）：http://blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html

于 2013-05-24T20:33:29.210 に答える