3

以下は、配列内の K 番目に小さい要素の前にある要素を見つけるために使用される選択ランク アルゴリズムの実装です。このプログラムはうまく動作することもありますが、スタック オーバーフロー エラー (コード スニペットの下のエラー) が原因で失敗することもあります。

public static int rand(int left, int right){
    return left+(int)(Math.random()*(double)(right-left));
}

public static int rank(int[] array, int left, int right, int rank){
    int pivot = rand(left, right);  
    int leftend = partition(array, left, right, array[pivot]);

    int size = leftend - left +1;
    if(size == rank+1){
        for(int i=0; i<=leftend; i++)
        System.out.print(array[i]+" ,");
        return 0;
    }else if(size > rank)
        return rank(array, left, leftend, rank);
    else return rank(array, leftend+1, right, rank - size);

}   

public static int partition(int[] array, int left, int right, int pivot){
    while(true){
        while(left <= right && array[left] <= pivot)
            left++;

        while(right >= left && array[right] > pivot)
        right--;

        if(left > right)
        return left-1;

        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

 }

エラー：

Exception in thread "main" java.lang.StackOverflowError
    at java.util.Random.nextDouble(Random.java:409)
    at java.lang.Math.random(Math.java:712)
    at mod.rand(mod.java:12)
    at mod.rank(mod.java:16)
    at mod.rank(mod.java:25)

おそらく rand() がこの問題を引き起こしていると思いますが、よくわかりません。また、それを修正する方法もわかりません。

4

3 に答える 3

2

randメソッドが左（含む）と右（含む）の間の数値を返すことを想定しています。ただし、Math.random() メソッドは、0.0 (含む) と 1.0 (含まない) の間の数値を返します。したがって、評価される部分配列のサイズが 2 の場合 (つまり、左 = 4 および右 = 5)、rand関数は結果として 4 しか返すことができません。関数でこの行を変更してrand、上限を含めることができるようにしてください。

return left+(int)(Math.random()*(double)(right-left));

為に

return left+(int)(Math.random()*(double)(right-left + 1));

于 2013-07-09T17:09:38.887 に答える