leetcode 4. Median of Two Sorted Arrays

问题描述:假设一批数分成了2个排好序的大小分别为m、n的数组A、B,如何快速找出所有数的中位数?
例如 A = {1,5,6,7},B = {2,3,4,8,9},则中位数为整体的第5大数 即A[2] = 4.
如果中位数有2个则取其平均值.

直接的做法是做一次归并排序(只需归并到一半),取合并后数组的中位数,复杂度为O(m+n).

受归并思路启发,考虑A的前2个元素组成的子集 {1,5} 以及 B的前5-2=3个元素组成的子集 {2,3,4}.
(也可以看A的前3个和B的前2个,只要加起来是5即可)
然后比较两边最大的两个A[2]=5 和 B[3]=4,有B[3]<A[2].
假设整体第5大数为K_{5},显然有A[2]>=K_{5}
因为A[2]已经至少是这两个子集的全部5个数的最大者了.
而A[1]与K_{5}的大小关系不能确定,都有可能.
有价值的是可以断定B[3]<K_{5},因为假如B[3]是全体第5大数或者更大,则小于B[3]的数至少存在5-1=4个,
但由于A[2]>B[3],那么全局小于B[3]的数只可能是除开A[2]和其自身的B[1]、B[2]、A[1] 这5-2=3个,矛盾.
那么寻找K_{5}就可以排除掉B[1]、B[2]、B[3]了,问题转换为求 A'=A={1,5,6,7} 和 B'={8,9} 的第 5-3=2大数
后者同样可以继续转换为求 A''={5,6,7} 和 B''=B'={8,9}的第1大数(最小值),即A''[1]=5

抽象到一般的情况,假设A={a_{1},a_{2},. . .,a_{m}},B={b_{1},b_{2},. . .,b_{n}},
A、B有序,我们要找出整体的第k大数K
考虑子集{a_{1},a_{2},. . .,a_{s}} 和 {b_{1},b_{2},. . .,b_{l}},其中s+l=k.
假如a_{s}<b_{l},则可以证明a_{s}<K. 则原问题归约为求 A'={a_{s+1},. . .,a_{m}},B'=B={b_{1},b_{2},. . .,b_{n}}的第k-s大数.

一般让s和l约为k的一半,则每次k减半,直到k=1,最终比较2个数取较小者即可.
可以看出是一个二分分治的算法, 对目标k值同时在2个数组上做二分查找

原题求中位数即k=(m+n)/2,可能要算k和k+1 2个,整体复杂度为O(log(m+n)).

发表评论

电子邮件地址不会被公开。