java - 为什么我的“中位数”算法总是错在几个位置？

Question

我的 Java 代码有问题...我已经盯着它看了 10 多个小时，但我只是找不到我犯的错误。

我的任务是通过将数组拆分为最大长度为 5 的数组并查找它们的中位数来实现“中位数的中位数”算法。然后你查找这些中位数的中位数并将你的主数组分成两部分，一个具有较小的值，另一个具有较大的值。通过这些数组的长度，您现在可以决定必须在哪个数组中查找哪个位置，然后重复算法，或者如果两个数组的大小相同，则完成。

但不知何故，在大多数情况下，我的算法与正确结果相差一两个位置。所以我认为，某处有一个小错误，可能只是循环的范围或类似的东西。因此，例如，我测试了数组{0,1,2,3,4,5,6,7,8}，因此中位数为 4，但我的程序以3结果作为响应。

我绝对知道，这是一大堆代码，我的问题可能不完全是 StackOverflow 的用途。同样在大多数情况下，我不喜欢让其他人查看我的代码，但我很绝望，因为我无法以某种方式找到我犯的错误。因此，如果你们中的某个人能够从中立的位置查看它，并可能给我一个小提示，为什么它没有按应有的方式工作，我将非常感激。

非常感谢

import java.util.Arrays;

public class MedianSelector {
    /**
     * Computes and retrieves the lower median of the given array of pairwise
     * distinct numbers using the Median algorithm presented in the lecture.
     * 
     * @param numbers array with pairwise distinct numbers.
     * @return the lower median.
     * @throw IllegalArgumentException if the array is {@code null} or empty.
     */
    public static int lowerMedian(int[] numbers) {
        // look out for wrong input
        if (numbers == null || numbers.length == 0) {
            throw new IllegalArgumentException("Input is not correct");
        }

        if (numbers.length == 1) {
            return numbers[0];
        }

        return getValueAtPosition(numbers, ((numbers.length + 1) / 2) - 1);
    }

    private static int getValueAtPosition(int[] numbers, int positionI) {

        // if the array is smaller then 6 elements
        // find median immediately
        if (numbers.length <= 5) {
            return smallArraySort(numbers);
        }

        // splitting the array into small arrays of maximum size 5
        int fields = 0;
        // checking if the array is split-able in only arrays of length 5
        // if not, then put the remaining values into an array of size <5
        if (numbers.length % 5 == 0) {
            fields = numbers.length / 5;
        } else {
            fields = numbers.length / 5 + 1;
        }
        // creating an array to hold all the smaller arrays
        int[][] splitted = new int[fields][];
        // filling the array with the smaller arrays if every smallArray has size 5
        if (numbers.length % 5 == 0) {
            for (int i = 0; i <= splitted.length - 1; i++) {
                int[] smallArray = new int[5];
                for (int j = i * 5; j < (i + 1) * 5; j++) {
                    smallArray[j % 5] = numbers[j];
                }
                splitted[i] = smallArray;
            }
        } else {
            // filling the array with the smallerArrays if the last array is smaller then 5
            for (int i = 0; i < splitted.length - 1; i++) {
                int[] smallArray = new int[5];
                for (int j = i * 5; j < (i + 1) * 5; j++) {
                    smallArray[j % 5] = numbers[j];
                }
                splitted[i] = smallArray;
            }
            int[] smallArray = new int[numbers.length % 5];
            for (int j = 0; j < numbers.length % 5; j++) {
                smallArray[j] = numbers[(numbers.length) - (numbers.length % 5) + j];
            }
            splitted[fields - 1] = smallArray;
        }

        // calculating the median of every small Arrays and writing them into a bigger
        // array
        int[] medianCollectorArray = new int[fields];
        for (int i = 0; i < splitted.length; i++) {
            medianCollectorArray[i] = smallArraySort(splitted[i]);
        }

        // calculating the median of the array of medians recursively
        int x = lowerMedian(medianCollectorArray);

        // counting the items that are smaller then the median
        int counterK = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] < x) {
                counterK++;
            }
        }

        // if the position of x is the position we are looking for, then we have found
        // the median
        if (counterK == positionI) {
            return x;

            // if the position we are looking for is left from x, we need to repeat the
            // algorithm in all elements, that are smaller then x and
            // find positionI there
        } else if (positionI < counterK) {
            int[] L1 = new int[counterK];
            int index = 0;
            for (int i = 0; i <= numbers.length - 1; i++) {
                if (numbers[i] < x) {
                    L1[index] = numbers[i];
                    index++;
                }
            }
            return getValueAtPosition(L1, positionI);
        } else {
            // if the position we are looking for is right from x, we need to repeat the
            // algorithm in all elements, that are bigger then x
            // and find (positionI - counterK +1) there
            int[] L2 = new int[numbers.length - (counterK + 1)];
            int index = 0;
            for (int i = 0; i <= numbers.length - 1; i++) {
                if (numbers[i] > x) {
                    L2[index] = numbers[i];
                    index++;
                }
            }
            return getValueAtPosition(L2, positionI - (counterK + 1));
        }
    }

    /**
     * This method calculates the median of an array with max. 5 elements.
     * 
     * @param array an array with maximum 5 elements
     * @return the median of this array
     */
    private static int smallArraySort(int[] array) {
        if (array == null || array.length > 5 || array.length <= 0) {
            throw new IllegalArgumentException("This array shall not be sorted by this method!");
        }

        // TODO: IMPLEMENT A SORTING ALGORITHM BY MYSELF

        // sorting the array an returning its median
        Arrays.sort(array);
        return array[(array.length - 1) / 2];
    }
}

标签： javaarrayssortingmedianmedian-of-medians

Answer 1

positionI我认为问题在于当长度numbers小于或等于 5时您会忽略。

你有：

if (numbers.length <= 5) {
    return smallArraySort(numbers);
}

我认为这应该是：

if (numbers.length <= 5) {
    Arrays.sort(numbers);
    return numbers[positionI];
}

只需进行此更改，您的代码似乎就可以产生正确的答案，至少在我尝试过的所有情况下。

只是一个小问题，但这一行：

return getValueAtPosition(numbers, ((numbers.length + 1) / 2) - 1);

可以简化为：

return getValueAtPosition(numbers, (numbers.length - 1) / 2 );