0

「ランダム化されたピボット」メソッドを使用して、指定された配列の中から K 番目の最小要素を見つけようとしました。
[コード]

public class FindKthMin {

// Find the Kth min elem by randomized pivot.
private static void exchange (int[] givenArray, int firstIndex, int secondIndex) {
    int tempElem = givenArray[firstIndex];
    givenArray[firstIndex] = givenArray[secondIndex];
    givenArray[secondIndex] = tempElem;
}
private static int partition (int[] givenArray, int start, int end, int pivotIndex) {

    // Debug:
    //System.out.println("debug: start = " + start);
    //System.out.println(">> end = " + end);
    //System.out.println(">> pivotIndex = " + pivotIndex);


    int pivot = givenArray[pivotIndex];
    int left = start - 1;
    int right = end;
    boolean hasDone = false;
    while (!hasDone) {
        while (!hasDone) {
            left ++;
            if (left == right) {
                hasDone = true;
                break;
            }
            if (givenArray[left] >= pivot) {
                // Exchange givenArray[left] and the givenArray[right].
                exchange(givenArray, left, right);
                break;
            }
        }
        while (!hasDone) {
            right --;
            if (left == right) {
                hasDone = true;
                break;
            }
            if (givenArray[right] < pivot) {
                // Exchange the givenArray[right] and the givenArray[left].
                exchange(givenArray, right, left);
                break;
            }
        }
    }
    givenArray[right] = pivot;
    // Debug:
    //System.out.println(">> split = " + right);
    //System.out.println();
    return right;
}
private static int findKthMin_RanP_Helper (int[] givenArray, int start, int end, int k) {
    if (start > end) return -1;
    // Generate a random num in the range[start, end].
    int rand = (int)(start +  Math.random() * (end - start + 1));
    // Using this random num as the pivot index to partition the array in the current scope.
    int split = partition(givenArray, start, end, rand);
    if (k == split + 1) return givenArray[split];
    else if (k < split + 1) return findKthMin_RanP_Helper(givenArray, start, split - 1, k);
    else return findKthMin_RanP_Helper(givenArray, split + 1, end, k);
}
public static int findKthMin_RanP (int[] givenArray, int k) {
    int size = givenArray.length;
    if (k < 1 || k > size) return -1;
    return findKthMin_RanP_Helper(givenArray, 0, size - 1, k);
}


// Main method to test.
public static void main (String[] args) {
    // Test data: {8, 9, 5, 2, 8, 4}.
    int[] givenArray = {8, 9, 5, 2, 8, 4};

    // Test finding the Kth min elem by randomized pivot method.
    System.out.println("Test finding the Kth min elem by randomized pivot method, rest = " + findKthMin_RanP(givenArray, 1));
}
}

しかし、結果は不安定で、正しい場合もあれば間違っている場合もあります。メソッド
の 5 行目を見てください。 これを に変更すると、結果は常に正しいです。これのどこが悪いのか本当にわかりません。 findKthMin_RanP_Helper
int split = partition(givenArray, start, end, rand);int split = partition(givenArray, start, end, end);

編集:
問題は「パーティション」に起因します。新しいパーティションは次のようになります。 

    private static int partition_second_version (int[] givenArray, int start, int end, int pivotIndex) {
    int pivot = givenArray[pivotIndex];
    int left = start;
    int right = end;
    while (left <= right) {
        while (givenArray[left] < pivot) left ++;
        while (givenArray[right] > pivot) right --;
        if (left <= right) {
            // Exchange givenArray[left] and givenArray[right].
            exchange(givenArray, left, right);
            left ++;
            right --;
        }
    }
    return left;
}


そして、次のfindKthMin_RanP_Helperように変更する必要があります。

    private static int findKthMin_RanP_Helper (int[] givenArray, int start, int end, int k) {
    if (start > end) return -1;
    // Generate a random num in the range[start, end].
    int rand = start +  (int)(Math.random() * ((end - start) + 1));
    // Using this random num as the pivot index to partition the array in the current scope.
    int split = partition_second_version (givenArray, start, end, rand);
    if (k == split) return givenArray[split - 1];
    else if (k < split) return findKthMin_RanP_Helper(givenArray, start, split - 1, k);
    else return findKthMin_RanP_Helper(givenArray, split, end, k);
}
4

1 に答える 1

1

パーティション ルーチンを簡素化できます...

  private static int partition(int[] givenArray, int start, int end, int pivotIndex) {
    final int pivot = givenArray[pivotIndex];
    int left = start;
    int right = end;
    while (left < right) {
        while (left < givenArray.length && givenArray[left] <= pivot) {
            left++;
        }

        while (right > -1 && givenArray[right] > pivot) {
            right--;
        }

        if (left >= right) {
            break;
        }
        exchange(givenArray, right, left);
    }
    return right;
}

あなたのコードに見られる 1 つのバグは、パーティション ルーチンです。最初の exchange 呼び出しでは、正しいインデックスが常に < ピボットの値を指すとは限りません。

于 2014-04-07T05:16:45.310 に答える