陈中正的网络日志

LeetCode: Median of Two Sorted Arrays

题目

https://oj.leetcode.com/problems/median-of-two-sorted-arrays/

分析

如果这道题的时间复杂度要求是O(m+n)的话, 就很简单了, 直接merge之后找出中位数即可。 

如果时间复杂度要求为O(log(m+n))的话, 可以把这道题转化为求第k小的问题。

1. 如果(m+n)是奇数的话, 中位数就是第(m+n)/2+1小; 如果(m+n)是偶数, 中位数就是第(m+n)/2小和第(m+n)/2+1小的平均数。

  1. 然后问题是如何求解第k小的数?

           假设有两个数组:   

           A[0], A[1], ......A[m-1]

           B[0], B[1], ......B[n-1]

           两数组合并后为

           C[0], C[1], ...... C[m+n-1]

           不妨假设m和n都大于k/2, 比较A[k/2-1]和B[k/2-1], 

           如果A[k/2-1] < B[k/2-1], 那么A[k/2-1]及其左侧的元素一定小于合并后的第k小的那个数(即C[k-1])

           为什么?

           可以通过反证来证明, 

           假设A[k/2-1]等于合并后第k小元素 (即C[k-1]), 

           那么实际最多有多少个元素比A[k/2-1]小呢? A[0], A[1]......A[k/2-2]以及B[0], B[1].......B[k/2-2], 共k-2个元素。 也就是说A[k/2-1]最好情况下是第k-1小元素(即C[k-2])

           这与假设矛盾, 因此假设不成立

           因此可以说, A[k/2-1]及其左侧元素一定小于合并后的第k小那个数, 这样就可以排除掉这一范围的数,从而缩小了问题规模。

  1. 再来考虑递归基

           当A为空或者B为空时, 返回B[k-1]或A[k-1]

           当k == 1时, 返回A[0]和B[0]中较小的那个数

           当A[k/2-1] == B[k/2-1]时, 返回A[k/2-1]

           否则的话, 就递归缩小问题规模。

代码

class Solution
{
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n)
    {
        if ((m + n) & 0x01)
            return findKth(A, m, B, n, (m + n) / 2 + 1);
        else
            return (findKth(A, m, B, n, (m + n) / 2) 
                    + findKth(A, m, B, n, (m + n) / 2 + 1)) / 2;
    }

    double findKth(int A[], int m, int B[], int n, int k)
    {
        if (m > n)
            return findKth(B, n, A, m, k);
        else if (m == 0)
            return B[k-1];
        else if (k == 1)
            return min(A[0], B[0]);
        else
        {
            int ALeftCount = min(k / 2, m);
            int BLeftCount = k - ALeftCount;

            if (A[ALeftCount-1] == B[BLeftCount-1])
                return A[ALeftCount-1];
            else if (A[ALeftCount-1] < B[BLeftCount-1])
                return findKth(A+ALeftCount, m-ALeftCount, 
                        B, n, k-ALeftCount);
            else//A[ALeftCount-1] > B[BLeftCount-1]]
                return findKth(A, m, 
                        B+BLeftCount, n-BLeftCount, k-BLeftCount);
        }
    }
};

参考

http://blog.csdn.net/yutianzuijin/article/details/11499917

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39156991

Categories:  OJ题解 

« LeetCode: Reverse Integer 『转』LeetCode题目难度频率分布 »