我正在尝试实现中位数算法/ BFPRT 算法的中位数。
main 中数组的检查输出是 5，但是我的代码甚至没有达到正确的输出（输出 -1，因为它没有达到 i>k 或 i<k 条件中的必要条件）。
任何帮助将不胜感激。
我越是绕开它，我的代码就越混乱。请原谅凌乱的代码：
import java.util.Arrays;
public class getMedian {
// Method for quickly returning a median
public static int getMedian(int[] list) {
Arrays.sort(list);
if (list.length == 0) {
System.out.println("Critical error, somehow passed empty list");
return 5000;
} else if (list.length <= 2) {
return list[list.length / 2];
} else {
return list[(list.length - 1) / 2];
}
}
// Method for getting the position of median from given list
public static int findMedianPos(int[] arr) {
int expectedMedianPos = 0;
if (arr.length % 2 == 0) {
expectedMedianPos = (arr.length / 2) - 1;
} else {
expectedMedianPos = (arr.length - 1) / 2;
}
return expectedMedianPos;
}
// Method for getting median of medians.
static int medianFinder(int[] arr, int[] orArr, int[] helperArr, int lowerBound, int upperBound, int medPos) {
int y = 0;
if (arr.length % 5 != 0) {
y = arr.length % 5;
} else {
y = 1;
}
int[] helper = new int[5];
int[] helper2 = new int[y];
int[] medians = new int[(int) Math.ceil(arr.length / 5.0)];
int medianPointer = 0;
if (arr.length <= 5) {
return partition(orArr, helperArr, getMedian(arr), medPos);
}
for (int i = lowerBound; i < upperBound; i++) {
helper[i % 5] = arr[i];
helper2[i % helper2.length] = arr[i];
if (i != lowerBound && (i + 1) % 5 == 0) {
medianPointer = medianPointer + 1;
}
if (i == upperBound - 1 && (i + 1) % 5 != 0) {
medians[medianPointer] = getMedian(helper2);
}
}
return medianFinder(medians, orArr, helperArr, 0, medians.length, medPos);
}
public static int partition(int[] partitionedLists, int[] orArr, int partitionElem, int medPos) {
int b = 0;
for (int i = 0; i < orArr.length; i++) {
if (orArr[i] == partitionElem) {
b = i;
}
}
int sizeL1 = 0;
int sizeL2 = 0;
for (int i = 0; i < partitionedLists.length; i++) {
if (partitionedLists[i] < partitionedLists[b]) {
sizeL1 = sizeL1 + 1;
}
if (partitionedLists[i] > partitionedLists[b]) {
sizeL2 = sizeL2 + 1;
}
}
int[] L1 = new int[sizeL1];
int[] L2 = new int[sizeL2];
int counterL1 = 0;
int counterL2 = 0;
for (int i = 0; i < partitionedLists.length; i++) {
if (partitionedLists[i] < partitionedLists[b]) {
L1[counterL1] = partitionedLists[i];
counterL1 = counterL1 + 1;
} else if (partitionedLists[i] > partitionedLists[b]) {
L2[counterL2] = partitionedLists[i];
counterL2 = counterL2 + 1;
}
}
int k = sizeL1 + 1;
int i = medPos;
if(i<k) {
if(sizeL1 <= 5) {
Arrays.sort(L1);
return L1[medPos - 1];
} else {
medianFinder(L1, orArr, orArr, 0, L1.length, i);
}
}
if(i>k) {
if(sizeL2 <= 5) {
Arrays.sort(L2);
return L2[medPos-1];
} else {
medianFinder(L2,orArr,orArr,0,L2.length,i);
}
}
return -1;
}
public static void main(String[] args) {
int[] numbers = {7,9,10,8,5,6,1,3,2,4};
System.out.println(medianFinder(numbers, numbers, numbers, 0, numbers.length, findMedianPos(numbers)+1));
}
}