0

我正在使用Foundations of Algorithms中的中位数算法选择第 k 个元素，但在 java 中实现它时遇到了麻烦。我得到一个数组越界错误，想知道是否有人可以帮助我正确实现这个算法。

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
    at test2.selection2(test2.java:23)
    at test2.select4(test2.java:16)
    at test2.partition2(test2.java:55)
    at test2.selection2(test2.java:27)
    at test2.select4(test2.java:16)
    at test2.partition2(test2.java:55)
    at test2.selection2(test2.java:27)
    at test2.select4(test2.java:16)
    at test2.main(test2.java:11)

这些是变量的值：

N size = 10
low = 0
high = 10
k = 3
arraysize = 10
r = 2
i = 1,2,3
first = 0,5,10
last = 4,9,11
lower = 7, 33
upper = 10, 44

-pivotitem
T size = 2
low = 0
high = 2
k = 1
arraysize = 10
r = 0

high==low [0]
list is empty

由于我的数组从大小 10 开始，r 将为 2。当从 pivotitem 再次调用 partition2 时，r 将为 0，导致大小为 0 的数组 T。然后 low 和 high 将等于 0，不返回任何内容，这就是我我得到了我的错误。我不知道为什么会这样，因为我的代码类似于书中的算法。

4

3 回答 3

0

原来是C-Code？partition2 用 & 调用

index& pivotpoint)

这意味着，一个引用，即调用者可以看到更改的结果。

您似乎使用静态的“枢轴点”来解决这个问题，但是您不能将其用作参数；它只会隐藏静态成员。

public static void partition2 (int[] list, int low, int high) // , int pivotpoint)
/* unchanged */
    thepivotpoint = j - 1;
    list = swap (mark, thepivotpoint, list);
}

它仍然不完整。

于 2011-03-08T11:07:10.847 回答
0

您的 swap 方法看起来好像将索引作为参数，但是您用值来提供它

list = swap (list[i], list[j], list);

这不是您错误的根源，并且在更改调用后错误仍然存​​在，但也许您多次出错。顺便说一句：代码去哪儿了？

于 2011-03-08T05:10:53.627 回答
0

我还有一些其他的改进，没有解决方案，但也许是更进一步的更好基础：

  • 并非所有变量都在方法的头部声明（pascal 风格）以缩小它们的范围。这使得推理代码更容易。
  • 我稍微统一了参数顺序(int[], int, ...)
  • 从if ... return else ....
  • 将 partition2 拆分为 2 个方法。
  • 添加了一种触发计数器的调试方法show，以在无限循环中停止。

  • 删除了对我没有帮助的评论。也许您可以添加更好的评论。

    import java.util.Arrays;

public class Pivot
{
    static int thepivotpoint;

    public static void main(String[] args)
    {
        int[] list = {17, 10, 44, 7, 7, 33, 24, 10, 48, 49 };
        thepivotpoint = 0;
        System.out.println (select4 (list, list.length, 3));
    }

    public static int select4 (int[] list, int high, int k)
    {
        return selection2 (list, 0, high, k);
        // return selection2 (list, 1, high, k);
    }

    public static int selection2 (int[] list, int low, int high, int k)
    {
        if (high == low)
            return list[low];
        partition2 (list, low, high);
        if (k == thepivotpoint)
            return list [thepivotpoint];
        if (k < thepivotpoint)
            return selection2 (list, low, thepivotpoint - 1, k);
        return selection2 (list, thepivotpoint + 1, high, k);
    }

    static int count = 0;
    public static void show (int [] T)
    {
        for (int i : T)
            System.out.print (i + "\t");    
        System.out.println ();  
        if (++count > 20) System.exit (1);
    }

    public static void partition2 (int[] list, int low, int high) 
    {
        int arraysize = high - low;
        int r = (int) Math.ceil (arraysize / 5);
        int [] T = new int[r+1];
        for (int i = 1; i <= r; i++)
        {
            int first = low + 5 * i - 5;
            int last = Math.min (low + 5 * i - 1, arraysize);
            T [i] = median (list, first, last);
        }
        show (list);
        approximateTheMedian (T, r, low, high, list);
    }

    public static void approximateTheMedian (int [] T, int r, int low, int high, int [] list) 
    {
        int pivotitem = select4 (T, r, (r + 1) / 2); 
        int j = low;
        int mark = 0;
        for (int i = low; i < high; i++)
        {
            if (list[i] == pivotitem)
            {
                list = swap (i, j, list);
                mark = j; //mark where pivotitem placed
                j++;
            }
            else if (list[i] < pivotitem)
            {
                list = swap (i, j, list);
                j++;
            }
        }
        thepivotpoint = j - 1;
        list = swap (mark, thepivotpoint, list);
    }

    public static int median (int[] list, int start, int end)
    {
        int [] copy = (int[]) list.clone ();
        Arrays.sort (copy);
        return copy [(start + end) / 2];
    }

    public static int[] swap (int one, int two, int[] list)
    {
        int dummy = list[one];
        list[one] = list[two];
        list[two] = dummy;
        return list;
    }
}
于 2011-03-08T16:55:30.447 回答