Description
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.
Clarification
The definition of the median:
The median here is equivalent to the median in the mathematical definition.
The median is the middle of the sorted array.
If there are n numbers in the array and n is an odd number, the median is A[(n-1)/2]A[(n−1)/2].
If there are n numbers in the array and n is even, the median is (A[n / 2] + A[n / 2 + 1]) / 2.
For example, the median of the array A=[1,2,3] is 2, and the median of the array A=[1,19] is 10.
Example
Example 1
Input:
A = [1,2,3,4,5,6]
B = [2,3,4,5]
Output: 3.5
Example 2
Input:
A = [1,2,3]
B = [4,5]
Output: 3
Challenge
The overall run time complexity should be O(log (m+n)).
思路：
1.最容易想的是将两个数组合成一个，然后求中位数，复杂度为O(m +n).
2.第二个是时间复杂度为O(log (m+n))，非常难想。
讲下面的算法之前，先说2个结论1：某个数组中有一半的元素不超过数组的中位数，有一半的元素不小于中位数（如果数组中元素个数是偶数，那么这里的一半并不是严格意义的1/2）。结论2：如果我们去掉数组比中位数小的k个数，再去掉比中位数大的k个数，得到的子数组的中位数和原来的中位数相同。
算法2：利用折半查找的思想，假设两个数组的中位数分别是vec1[m1], vec2[m2] 本文地址
1、如果vec1[m1] = vec2[m2] ，那么刚好有一半元素不超过vec1[m1]，则vec1[m1]就是要找的中位数。
2、如果vec1[m1] < vec2[m2] 根据结论1很容易可以推理出，这个中位数只可能出现在vec1[n1/2,…,n1-1]或vec2[0,…,(n2-1)/2]中，那么vec1[n1/2,…,n1-1]和vec2[0,…,(n2-1)/2]的中位数是不是和原来两个数组的中位数相同呢？根据结论2，如果原数组长度相等，即n1=n2，那么中位数不变；如果长度不相等，vec2中去掉的大于中位数的数的个数 > vec1中去掉的小于中位数的数的个数 ，则中位数不一定不变。因此我们要在两个数组中去掉相同个数的元素。如下图所示，假设n1 < n2, 两个数组都去掉n1/2个元素，则子数组vec1[n1/2,…,n1-1]和vec2[0,…,n2-1-n1/2]的中位数和原来的中位数相同，图中红色方框里是去掉的元素。
注意：在n1<n2的假设下，不管我们是求上中位数还是下中位数，我们每次去掉的元素都是n1/2（整数除法）个。例如vec1 = [1,3,5,7],vec2 = [2,4,6,8], 如果我们要求的是上中位数，m1 = m2 =1，即3 < 4, 要删掉vec1的前半段，这里vec1[m1] = 3 要不要删除呢，我们只要判断一下3能否可能成为中位数，假设3是中位数，不超过3的数只有3个（1,2,3），总得元素有8个，因此3不可能成为上中位数，我们可以在vec1中删除2两个元素。如果是求下中位数，即m1 = m2 = 2，即5 < 6,删除vec1前半段时要不要删除5呢？注意到比不超过5的数有5个，不低于5的数有4个，因此5有可能成为下中位数，因此5不能删除，vec1中只能删除左边两个元素。同理当vec1的个数是奇数时，vec1的中位数永远不能删除，即只能删除vec1的n1/2（整数除法）个元素
3、如果vec1[m1] > vec2[m2] ，同上分析，中位数只可能出现在vec1的前半段或vec2的后半段。如下图所示，两个数组分别去掉n1/2个元素后，子数组vec1[0,…,n1/2-1]和vec2[n1/2,…,n2-1]的中位数和原来的中位数相同
代码：
1.
2.
网友评论