我为学校写了一个java代码来计算数组的中位数。我们对此有一些测试用例。第一列是输入，第二列是预期输出，第三列是实际输出。这个案子有什么特别之处吗?我已经在这段代码上工作了很长时间，现在慢慢地，但我肯定会感到沮丧。我真的不知道我的代码在什么地方或者为什么不能在这个特定的场景中工作。代码如下:
/**
* This class calculates the median of a list to use it in quicksort for a runtime of O(log(n));
* @author Niklas
*
*/
public class Median {
/**
* The position i.
*/
private static int positionI = -1;
/**
* a help array for the quicksort algorithm.
*/
private static int[] quicksortArray;
/**
* Computes and retrieves the lower median of the given array of numbers using
* the Median algorithm presented in the lecture.
*
* @param input numbers.
* @return the lower median.
* @throw IllegalArgumentException if the array is {@code null} or empty.
*/
public static int lowerMedian(int[] numbers) {
if (numbers.length == 0 || numbers == null) {
throw new IllegalArgumentException("Array must contain values");
}
// avoiding that positionI is part of the recursion
if (positionI == -1) {
positionI = (int) Math.floor((double) ((numbers.length + 1) / 2));
}
// Step 1: dividing the list into groups.
int[] medians = new int[(int) Math.ceil((float) numbers.length / 5)];
int[] subArray = new int[5];
int positionForMedianArray = 0;
// the end case that the array is < 5.
if (numbers.length <= 5) {
sortArray(numbers);
if (positionI <= numbers.length) {
return numbers[positionI - 1];
}
return numbers.length % 2 == 0 ? numbers[(numbers.length / 2) - 1] : numbers[numbers.length / 2];
}
for (int i = 0; i < numbers.length; i += 5) {
if (numbers.length < i + 5) {
subArray = Arrays.copyOfRange(numbers, i, numbers.length);
} else {
subArray = Arrays.copyOfRange(numbers, i, i + 5);
}
// Step 2: calculate the median of each subArray.
sortArray(subArray);
medians[positionForMedianArray] = subArray.length % 2 == 0 ? subArray[subArray.length / 2 - 1]
: subArray[subArray.length / 2];
positionForMedianArray += 1;
}
// Step 3: calculate x recursively
int x = lowerMedian(medians);
// Step 4: partioniate the lists.
// computing how big the arrays have to be because arraylists doesnt work as
// good in this code.
int countS = 0;
int countG = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] < x) {
countS += 1;
} else if (numbers[i] > x) {
countG += 1;
}
}
// creating the arrays with the right size.
int[] smaller = new int[countS];
int[] greater = new int[countG];
countS = 0;
countG = 0;
// filling the Arrays (L1 and L2).
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] < x) {
smaller[countS] = numbers[i];
countS += 1;
} else if (numbers[i] > x) {
greater[countG] = numbers[i];
countG += 1;
}
}
int k = smaller.length + 1;
// for testing
// System.out.println("nnumbers: " + Arrays.toString(numbers));
// System.out.println("position i: " + positionI);
// System.out.println("SubArray " + (positionForMedianArray) + ": " + Arrays.toString(subArray));
// System.out.println("Median Array im Durchlauf " + (positionForMedianArray) + ": " + Arrays.toString(medians));
// System.out.println("x: " + x);
// System.out.println("L1: " + Arrays.toString(smaller));
// System.out.println("L2: " + Arrays.toString(greater));
// System.out.println("Position k: " + k);
if (positionI < k) {
return lowerMedian(smaller);
} else if (positionI > k) {
positionI -= k;
return lowerMedian(greater);
}
return x;
}
/**
* Sorts the given array in an inefficent way.
*
* @param numbers the array to sort.
*/
private static void sortArray(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < numbers.length; j++) {
if (numbers[i] < numbers[j]) {
int tempVar = numbers[j];
numbers[j] = numbers[i];
numbers[i] = tempVar;
}
}
}
}
我将感激任何帮助!
我不知道为什么你计算低中位数的方法如此复杂。你所需要做的就是对数字列表进行排序，如果列表有奇数个值，那么在<array length> / 2返回值，如果列表有偶数个值，那么在(<array_length> / 2) - 1返回值。对于输入列表的排序，您可以实现自己的快速排序算法，也可以使用Arrays.sort。下面是使用Java内置排序方法计算中位数下限的潜在方法。
public static int lowerMedian(int[] numbers) {
Arrays.sort(numbers, 0, numbers.length);
int length = numbers.length;
if (length == 0) {
return 0;
} else if (length % 2 == 0) {
return numbers[(length / 2) - 1];
} else {
return numbers[length / 2];
}
}