两个不同大小的排序阵列的中位数
问题描述:
我试图找到两个不同大小的排序阵列的中位数。但是有一些情况不起作用,我无法弄清楚为什么。我已经在下面列出了我的实现。两个不同大小的排序阵列的中位数
我知道网上有类似的解决方案。但是我刚刚开始学习算法,所以我想尽可能多地去做。提前感谢您的帮助!
public double median(Point[] arr, int start, int end) {
int n = end - start + 1;
if (n % 2 == 0) {
return (double) (arr[start + (n/2)].getSz() + arr[start + (n/2) - 1].getSz())/2;
}
else {
return (double) arr[start + (n/2)].getSz();
}
}
public double getMedian(int aStart, int aEnd, int bStart, int bEnd) {
int m = aEnd - aStart + 1;
int n = bEnd - bStart + 1;
double median = 0;
if (m == 0 && n > 0) {
return median(arr2, 0, bEnd);
}
if (m > 0 && n == 0) {
return median(arr1, 0, aEnd);
}
if (m == 1 && n == 1) {
return (double) (arr1[0].getSz() + arr2[0].getSz())/2;
}
if (m == 2 && n == 2) {
median = (double) (Math.max(arr1[aStart].getSz(), arr2[bStart].getSz()) + Math.min(arr1[aEnd].getSz(), arr2[bEnd].getSz()))/2;
return median;
}
double m1 = median(arr1, aStart, aEnd);
double m2 = median(arr2, bStart, bEnd);
if (m1 == m2) {
return m1;
}
if (m1 < m2) {
if (m % 2 == 0) {
aStart = aStart + (m/2) - 1;
index = 1;
}
else {
index = 2;
aStart = aStart + m/2;
}
bEnd = bStart + n/2;
}
else {
if (n % 2 == 0) {
index = 3;
bStart = bStart + n/2 - 1;
}
else {
index = 4;
bStart = bStart + n/2;
}
aEnd = aStart + m/2;
}
return (getMedian(aStart, aEnd, bStart, bEnd));
}
这里的一个例子的量,逻辑场所:
ARR1 = 6,20,28,29,36,41
ARR2 = 14,25,33,47,53,66,79,98
正确位数= 34.5
预估中值= 31
答
看起来像有算法中的一些问题。
首先0被替代地使用A启动和bStart的在几个地方:
if (m == 0 && n > 0) {
return median(arr2, ->0<-, bEnd);
}
if (m > 0 && n == 0) {
return median(arr1, ->0<-, aEnd);
}
if (m == 1 && n == 1) {
return (double) (arr1[->0<-].getSz() + arr2[->0<-].getSz())/2;
}
其次;在最后一个块中,你必须小心地抛出高于中位数的值,如下所示。
if (m1 < m2) {
if (m % 2 == 0) {
aStart = aStart + (->m<-/2) - 1;
index = 1;
}
else {
index = 2;
aStart = aStart + ->m<-/2;
}
bEnd = bStart + ->n<- /2;
}
而且你也不能抛出最接近中位数的数值在偶数个数据上计算的值。希望有所帮助。
答
拿到两个排序数组一个和乙的中位数,你需要弄清楚如何既阵列分成低部分和高部分,让所有的低部分元素是< =所有高部分元素和低部分和高部分中的元素总数相同(1以内)。
低元素将包括一些数量的元件X从甲,和(则为a.length + b.length个)/ 2 - 从乙 X元件。
要查找x,请对x的可能值进行二分查找。设MID =(A.length + B.length)/ 2。然后,如果猜测x,如果A [x-1]> B [MID-x]则x太大。否则它不是太大。该条件足以让您在每次迭代中将值的范围缩小一半。
一旦知道其中阵列被划分,就知道最大值(A [X-1],B [MID-X-1])是在低的部分的最高元件,和分钟(A [x],B [MID-x])是高部分中最低的元素,这就是所有您需要计算的中位数。
是的,这有助于很多!现在完美运作。非常感谢你。 – sh1291