Median of Two Sorted Arrays

题目意思:两个有序数组nums1和nums2,其大小分别是m和n.求其中位数. 比如[1,2,3]的中位数是2,[1,2,3,4]的中位数是(2+3)/2=2.5.

Solution

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
class Solution
{
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        int m = nums1.size(),n = nums2.size();
        if((m + n) % 2 == 0)
            return (FindKth(nums1,nums2,(m + n) / 2) + FindKth(nums1,nums2,(m + n) / 2 + 1))  / 2.0;
        else
            return FindKth(nums1,nums2,(m + n + 1) / 2);
    }
    //找到第k个最大的数,K应小于等于m+n,这里未做验证
    int FindKth(vector<int> &M,vector<int>& N,int K)
    {
        int m = M.size(),n = N.size();
        //设置M为较短的数组
        if(m > n) return FindKth(N,M,K);
        //边界条件:注意下面两行不能互换,因为可能在K == 1时,较短的数组M可能为空
        //比如M=[1,2] N=[3,4]
        if(m == 0) return  N[K - 1];
        if(K == 1) return min(M[0],N[0]);
        //M和N的指针分别设置为pm,pn,使得pm+pn=K
        int pm = min(K / 2,m);
        int pn = K - pm;
        //如果M上的一段必定位于前K个数中
        if(M[pm - 1] < N[pn - 1])
        {
            vector<int> vec(M.begin() + pm,M.end());
            return FindKth(vec,N,K - pm);
        }
        //否则在N上的一段必然属于前K个数中
        else
        {
            vector<int> vec(N.begin() + pn,N.end());
            return FindKth(M,vec,K - pn);
        }
    }
    //调试函数
    void PrintVector(vector<int> vec)
    {
        for(vector<int>::iterator pos = vec.begin(); pos != vec.end(); ++pos)
            if(pos + 1 == vec.end()) cout<<*pos<<endl;
            else cout<<*pos<<"  ";
    }
};
//=======================Driver===========================
int main()
{
    int M[] = {1,2};
    int N[] = {3,4};
    vector<int> nums1(M,M + sizeof(M) / sizeof(int));
    vector<int> nums2(N,N + sizeof(N) / sizeof(int));
    Solution s;
    cout<<s.findMedianSortedArrays(nums1,nums2)<<endl;
    //cout<<s.SearchPos(nums1,2);
    return 0;
}


/*
===========complexity==============
Time Complexity:O(log(m+n))
Space Complexity:O(1)
===========makefile=================
all:
    @g++  solve.cpp -o   solve
    @./solve
clean:
    rm -f solve
    reset
===========leetcode accepted========
2080 / 2080 test cases passed.
Status: Accepted
Runtime: 32 ms
Submitted: 0 minutes ago
===========submission date=========
2017-01-09 Mon 11:03 PM
*/

Analysis

这道题的分析我已经不想写太详细了,因为实在是不想写了,这两天全耗在这道题上了.大致说一下意思.

这里的核心思想是,把找中位数转换为求第K小数问题.本题并没有说两个有序数组到底是怎样的有序,都是升,还是都是降? 但这没有关系.无论都是升还是都是降,不过是分别对应第K小,第K大的问题了,这不影响中位数的求解

如果说m+n为偶数,那么中位数就是数组合并后,中间的两个数的平均数.也就是第(m+n)/2个和第(m+n)/2+1个数的平均数.

如果说m+n为奇数,那么中位数就是数组合并后,中间的那个数.

问题转化后,就是求第K数的问题,这也是个难点.

如下图: 数组M和N的左侧共取K个数,M上取前pm=K/2个数,N上取前pn=K-K/2个数,这样的话可以通过比较M[pm-1]和N[pn-1]来确定前K个数中近似一半的数. 因为,当M[pm-1] <N[pn-1]时,M和N都是有序数组,那么知道M的左半部分小于M和N的右半部分,因此,M的前K/2个数小于m+n中的m+n-K个数, 那么这K/2个数一定是位于前K个数之中.因而再递归的处理M[K/2-1,..,m-1]以及N[0,n-1]即可.类似的,如果M[pm-1] >= N[pn-1], 那么可以递归的处理N[K-K/2-1,..,n-1]以及M[0,m-1].是不是很巧妙,我觉得是的,太TM聪明了,这种做法!!那么时间复杂度呢? 看起来不是很好计算.但是我们是要找第K个数,而且是二分法,K就近似等于(m+n)/2,所以时间复杂度就是O(log((m+n)/2)), 也就是O(log(m+n)).

这里面几个细节问题:

Supplement

以前碰到过一道类似的题,不过说的是中位数取m/2处的数,对于这种类型,有一种分治的思想值得说明, 下面便是对这种思想的论述以及证明.我本来也尝试应用于此题,但是以失败告终,因为要考虑的边界情况太多了. 为了方便描述,作下图(用inkscape画了好长时间....没办法,强迫症...):
图1

要求$\log_2(m+n),CS中一般写作\log(m+n)$的时间,那就是二分法.那么这里怎么个二分法呢?且听我慢慢说来.

两个有序的数组M,N,不妨都设为非递减数组,对应的长度分别是为m,n.如上图所示,分别用两个线段来表示这两个数组. 中位数是位于中间的那个数,也就是说,中位数左右两侧的数的个数是相等的.但是由于数组的元素数目可能是偶数个, 那么中位数就夹在中间两数之间,不属于数组元素,这样不好分析问题.于是我们取位于数组中间或者中间靠左的那个数为一个分界点来研究问题. 该数要么是中位数,要么是中位数左毗连的第一个整数,我们记该数为K.那么K的索引用取整函数可以表示为$im=\lfloor\frac{m+1}{2}\rfloor$, 类似地我们可以得到$in$.

那么易知,当$KM>KN$时,上图左半部分的虚线箭头为一个非递减数组,而n本身是一个非递减数组.由这些条件,我们有结论:

$KM>KN时$:

只要我们能证明上述结论,那么一次排除了整体的约一半元素,因此时间复杂度就是$\log(m+n)$.下面就让我们用数学来严格的证明一下. 这里我用的是反证法,略微用到了一些具体数学上的东西.

假如说中位数位于数组N的左侧,中位数最靠右的情况下是位于数组N的(im-1,im)之间,这里姑且这么称呼了, 显然,这种情况下中位数的值为(N[in-1]+N[in])/2.而我们的假设是:

中位数位于数组N的(im-1,im)之间

无论何种情况,中位数左侧数的个数ML以及中位数右侧的数的个数MR一定为$\lfloor \frac{m+n}{2} \rfloor $,而这种假设之下, 又可以得知中位数右边的数MR至少为$(1+m-im)+(1+n-in)=2+m+n-im-in$.即: $$ML=MR=\lfloor \frac{m+n}{2} \rfloor\hspace{1cm}且\hspace{1cm} MR \geq 2+m+n-im-in $$ 于是有: $$\lfloor \frac{m+n}{2} \rfloor \geq 2+m+n-im-in $$ 也即: $$ 2+m+n-im-in - \lfloor \frac{m+n}{2} \rfloor \leq 0$$ 代入im和in的表达式我们有: $$ 2+m+n- \lfloor\frac{m+1}{2}\rfloor - \lfloor\frac{n+1}{2}\rfloor - \lfloor \frac{m+n}{2} \rfloor \leq 0$$
来一个小插曲,我们知道$\forall x ,有x=\lfloor x \rfloor + \{x\}$,这里$\{x\}$表示实数x的小数部分.因此: $$\forall x,y \in R, x+y=\lfloor x \rfloor + \{x\} + \lfloor y \rfloor + \{y\}$$ 于是: $$ \lfloor x+y \rfloor=\lfloor x \rfloor + \lfloor y \rfloor + \lfloor \{x\} + \{y\} \rfloor$$ 因此: $$ \lfloor x+y \rfloor \geq \lfloor x \rfloor + \lfloor y \rfloor $$ 易得: $$ -\lfloor x \rfloor - \lfloor y \rfloor \geq -\lfloor x+y \rfloor $$
好的,对不等式 $$ 2+m+n- \lfloor\frac{m+1}{2}\rfloor - \lfloor\frac{n+1}{2}\rfloor - \lfloor \frac{m+n}{2} \rfloor \leq 0$$ 的左侧我们有: $$ 2+m+n- \lfloor\frac{m+1}{2}\rfloor - \lfloor\frac{n+1}{2}\rfloor - \lfloor \frac{m+n}{2} \rfloor \geq 2+m+n- \lfloor\frac{m+1}{2} + \frac{n+1}{2} + \frac{m+n}{2} \rfloor = 2 + m + n - \lfloor m+n-1 \rfloor =1 $$ 于是有 $$ 2+m+n- \lfloor\frac{m+1}{2}\rfloor - \lfloor\frac{n+1}{2}\rfloor - \lfloor \frac{m+n}{2} \rfloor \geq 1$$ 矛盾因此得出.所以我们的假设是不成立的.那么很显然,中位数肯定也不可能位于[1,2,3,...,in-1]的某个整点索引或者某个单位长度区间内, 因为要是位于[1,2,3,...,in-1]之中,那么上述不等式左边的下界会越来越大(最小的下界是1),肯定不会小于等于0,这也是为什么选择最靠右侧的中位数为假设.

类似地,我们可以证明中位数不可能位于数组M的右半侧部分.

至此,我们证明了我们的结论.该结论对应于图1的左半部分,红叉表示中位数不可能存在的区域.同样的道理,也有图1左侧的情况,因此总的结论如下:

1)$KM>KN时$: 2)$ KM < KN 时 $: 3)$ KM == KN时 $:

Reference
1.http://www.lifeincode.net/programming/leetcode-median-of-two-sorted-arrays-more-elegant-solution/
2.http://yucoding.blogspot.jp/2013/01/leetcode-question-50-median-of-two.html
本博客不设置评论功能.如有问题可以通过我的邮箱dXAyZ2Vla0AxNjMuY29tCg==或者新浪微博:bugnofree联系我.