选择等级算法

debugcn 发表于 Dev

城市

下面是选择等级算法的实现，该算法用于查找数组中第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（）导致了此问题，但我不确定。我也不知道如何解决它。

ZePoLiTaT

我假设您想让您的rand方法返回一个介于left（包括）和right（包括）之间的数字。但是，Math.random（）方法返回一个介于0.0（含）和1.0（不含）之间的数字。因此，在要评估的子数组的大小为2的情况下（即：left = 4和right = 5），该rand函数将只能返回4。尝试在rand函数中更改此行，以确保它可以包含上限：

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

为了

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

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。