两个排序数组的中位数

Question

我的问题是参考此链接的方法2 .这里给出了两个相等长度的排序数组,我们必须找到合并的两个数组的中位数.

Algorithm:

1) Calculate the medians m1 and m2 of the input arrays ar1[] 
   and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
     return m1 (or m2)
3) If m1 is greater than m2, then median is present in one 
   of the below two subarrays.
    a)  From first element of ar1 to m1 (ar1[0...|_n/2_|])
    b)  From m2 to last element of ar2  (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one    
   of the below two subarrays.
   a)  From m1 to last element of ar1  (ar1[|_n/2_|...n-1])
   b)  From first element of ar2 to m2 (ar2[0...|_n/2_|])
5) Repeat the above process until size of both the subarrays 
   becomes 2.
6) If size of the two arrays is 2 then use below formula to get 
  the median.
    Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

Example:

   ar1[] = {1, 12, 15, 26, 38}
   ar2[] = {2, 13, 17, 30, 45}

For above two arrays m1 = 15 and m2 = 17

For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.

   [15, 26, 38] and [2, 13, 17]
Let us repeat the process for above two subarrays:

    m1 = 26 m2 = 13.
m1 is greater than m2. So the subarrays become

  [15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
                       = (max(15, 13) + min(26, 17))/2 
                       = (15 + 17)/2
                       = 16

我理解他们如何排除数组的一半,并说中间元素将特别是数组的一半,即步骤1,2,3,4,5.

But what I can't fathom, how can they say that the median of the merged arrays would be the median of the merged arrays resulting after pruning the halves of the arrays i.e. the median of merge array of {1, 12, 15, 26, 38} and {2, 13, 17, 30, 45} would be the median of the merge array of {2,13,17} and {15, 26, 38}.

Please explain. Thanks in advance.

Answer 1

让我帮你想象一下.让我们说它是案例3,其他案例也是如此.这意味着我们已经确定中位数存在于ar1的上半部分或ar2的后半部分.现在问题是为什么这两半的中位数与原始数组的中位数相同,正确.

因此可视化将这些相关的一半按排序顺序放在一起并找到其中位数.现在把另一半留在这张图片中,他们会去哪里.AR2的前半部分,所有n/2个元素一定要到这个新的中位数的顶部和ARR1下半年所有n/2个元素将不得不走这位数以下(确切位置是不重要的中位数).这意味着它仍然是一个中位数,因为在它上面和下面添加了相同数量的元素.因此,两个新半部的中位数与原始集的中位数相同.

更准确地说,让我们看看为什么ar2的前半部分(剩下的一半)必须超过新的中位数.情况就是这样,因为当我们将所有元素放在一起时,m2必须超过新的中位数(因为m2 <m1),这意味着ar2的所有前半部分也必须超过新的中位数.换句话说,如果m是2个所选半部的新中值,则m2 <m => ar2的所有前半部分<m.ar1下半部分的类似论点.这意味着新的中位数m将保持整个集合的中位数.

仔细观察你的算法.虽然方法是正确的,但算法中可能会有轻微的错误,同时处理奇数和偶数情况,因此在实施时要小心.

Answer 2

由于等长约束，当我们比较两个中位数时，我们可以安全地丢弃值。

如果 m2 大于 m1，我们知道数组 2 必须比数组 1 包含更多数量的大值，因此只要我们从数组 2 中丢弃相同数量的大值，m1 以下的所有小值都不会有意义.结果将是一个较短的数组，但我们正在寻找的中位数没有改变，因为我们从两侧进行了同等修剪。

这有点让我想起通过双手分开支撑物体，然后慢慢地将它们放在一起，以保持物体平衡来找到物体的质心。