两个不同大小的排序阵列的中位数

Question

我试图找到两个不同大小的排序阵列的中位数。但是有一些情况不起作用，我无法弄清楚为什么。我已经在下面列出了我的实现。

我知道网上有类似的解决方案。但是我刚刚开始学习算法，所以我想尽可能多地去做。提前感谢您的帮助！

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

Answer 1

看起来像有算法中的一些问题。

首先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; 
} 

而且你也不能抛出最接近中位数的数值在偶数个数据上计算的值。希望有所帮助。

Answer 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]）是高部分中最低的元素，这就是所有您需要计算的中位数。