两个长度不同的排序数组的中位数 [英] Median of two sorted arrays of different length

问题描述

我试图理解在O（log（n + m））中解决此问题的算法，其中n和m是数组的长度。我已自由发布了指向该算法的解释的链接：

I am trying to understand the algorithm that solves this problem in O(log(n+m)) where n and m are the lengths of the arrays. I have taken the liberty to post the link to the explanation of this algorithm:

> https://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/

对于我来说，很难完全消化该算法背后的思想。我可以看到，其想法是将数组之一的长度减少到1或2，然后应用基本情况。基本案例是有道理的，但我想知道是否可以忽略n = 2的基本案例，而仅对n = 1进行处理。我也不了解其余案例。对我来说看起来很奇怪，我们必须从头开始将数组B []剪切到idx。这很奇怪，因为idx可以等于B []的长度，所以我们将忽略整个数组。

It's so hard for me to digest completely the idea behind this algorithm. I can see that the idea is to reduce the length of one of the arrays to either 1 or 2 and then apply the base cases. The base cases make sense, but I wonder if one can omit the base case for n = 2 and just work on n = 1. I also don't understand the remaining cases part. It looks so weird to me that we have to cut the array B[] from the start to idx. It's weird because idx can be equal to the length of B[], so we would be ignoring the whole array.

推荐答案

TL; DR：

主要思想是只要删除肯定大于或等于中位数的N个元素，就可以删除其中的N个小于或等于中位数的元素。

The main idea is that you may delete N elements that are surely smaller than (or equal to) the median from your number set, as long as you delete the same amount that are surely greater or equal.

让我们用一个示例进行解释：

Let's explain it with an example:

A = [1 2 3 9 10]，B = [3 4 5 6 7 8 9]

A=[1 2 3 9 10], B=[3 4 5 6 7 8 9]

标记为中间的元素：

A = [1 2 3 9 10]，B = [3 4 5 6 7 8 9]

A=[1 2 3 9 10], B=[3 4 5 6 7 8 9]

总体中位数在3到6之间（含3和6）。因此，如果我们删除两个小于3的元素，并且删除两个大于6的元素，我们的中位数仍然相同。我们从A删除较小的元素，而从B删除较大的元素：

The overall median will be between 3 and 6, inclusive. So, if we delete two elements smaller than 3, and two elements greater than 6, we'll still have the same median. The smaller elements we delete from A, and the greater ones from B:

A = [3 9 10]，B = [3 4 5 6 7]

A=[3 9 10], B=[3 4 5 6 7]

现在，我们删除一个大于9的元素（从A）到一个小于5的元素（从B）：

Now we delete one element greater than 9 (from A) and one smaller than 5 (from B):

A = [3 9]，B = [4 5 6 7]

A=[3 9], B=[4 5 6 7]

我们到达了案例4（较小的数组有2个元素）：算法要求

We reached Case 4 (smaller array has 2 elements): the algorithm calls for the median of

B [M / 2]，B [M / 2 – 1]，max（A [0]， B [M / 2 – 2]），min（A [1]，B [M / 2 + 1]）

B[M/2], B[M/2 – 1], max(A[0], B[M/2 – 2]), min(A[1], B[M/2 + 1])

是B [2]，B [1 ]，max（A [0]，B [0]），min（A [1]，B [3]）

being B[2], B[1], max(A[0], B[0]), min(A[1], B[3])

是6，5，max（3 ，4），min（9,7）

being 6, 5, max(3,4), min(9,7)

是[6 5 4 7]

being [6 5 4 7]

该数组是5.5。那是正确的结果。

The median of that array is 5.5. And that's the correct result.

这篇关于两个长度不同的排序数组的中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！