下面是我的代码,用于尝试了解中位数算法的中位数(使用大小为5的块)。我知道如何获取输入的中位数,但是我不确定如何对块进行编码以保持递归输入,直到获得中位数为止。然后,在获得中位数之后,我不确定如何将其用作枢轴以丢弃无用的信息来划分输入。getMediansArray
返回大小为ceil(input.length / 5)的数组,并且getMedians
仅返回数组的中位数(仅用于长度<= 5的数组)。
public static int[] findKthElement(int[] input, int k) {
int numOfMedians = (int) Math.ceil(input.length/5.0);
int[] medians = new int[numOfMedians];
medians = getMediansArray(input, medians)
// (1) This only gets the first iteration of medians of the
// input. How do I recurse on this until I just have one median?
// (2) how should I partition about the pivot once I get it?
}
public static int[] getMediansArray(int[] input, int[] medians) {
int numOfMedians = (int) Math.ceil(input.length/5.0);
int[] five = new int[5];
for (int i = 0; i < numOfMedians; i++) {
if (i != numOfMedians - 1) {
for (int j = 0; j < 5; j++) {
five[j] = input[(i*5)+j];
}
medians[i] = getMedian(five);
} else {
int numOfRemainders = input.length % 5;
int[] remainder = new int[numOfRemainders];
for (int j = 0; j < numOfRemainders; j++) {
remainder[j] = input[(i*5)+j];
}
medians[i] = getMedian(five);
}
}
return medians;
}
public static int getMedian(int[] input) {
Arrays.sort(input);
if (input.length % 2 == 0) {
return (input[input.length/2] + input[input.length/2 - 1]) / 2;
}
return input[input.length/2];
}
中位数的中位数基本上只是改进的快速选择算法(http://en.wikipedia.org/wiki/Quickselect)。快速选择的平均时间复杂度为O(n),但对于棘手的输入,它可能会降低到O(n ^ 2)。
找到中位数的中位数后,您要做的只是快速选择算法的迭代。中位数的中位数具有很好的属性,它将始终大于30%的元素并且小于30%的元素。这保证了使用中位数的中位数作为枢轴的快速选择将在最差的O(n)时间复杂度下运行。请参阅:http : //en.wikipedia.org/wiki/Median_of_medians
我建议您从实现快速选择开始。完成此操作后,您可以使用已经在快速选择的每个步骤中选择数据透视的代码。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句