美文网首页
【LeetCode】寻找两个已排序数组中的中位数

【LeetCode】寻找两个已排序数组中的中位数

作者: aniegai | 来源:发表于2018-05-10 17:41 被阅读0次

    原题链接:https://leetcode.com/problems/median-of-two-sorted-arrays/description/

    两个已排序数组A[m]和B[n],找到它们两个的中位数。
    例子:
    [1,3],[2] -> result = 3
    [1,3], [2,4] -> result = (2+3)/2 = 2.5
    核心要求是算法复杂度为O(log (m+n))

    (以下仅为自己的思路记录,还未编码进行验证)
    解法思路:
    由于复杂度要求为O(log (m+n)),因此考虑用二分的思路进行求解。
    假设A和B合并后的中位数为x(若有两个则为x,y),那么比x(x、y)小的数共有(m+n-1)/2 (向下取整)个,记为k个,同样比x(或者x和y)大的数也有k个。
    那么我们可以把思路调整为,不断二分筛掉这些明显较小和较大的数,最后剩下的就是我们要找的中位数:
    第一步,取A的第k/2个数A[k/2 -1]和B倒数第k/2个数B[n- k/2],这样可以找出比A[k/2 -1]和B[n- k/2]都小和都大的数,并丢弃。不妨设 A[k/2 -1] < B[n-k/2],那么A[0]~A[k/2 -1]就是可以筛掉的较小的数,B[n-k/2] ~B[n]就是可以筛掉的较大的数。
    第二步,这个时候未被筛掉的较小和较大的数都还有k/2个,那么我们继续进行二分,取筛选后的A、B数组继续取其第k/4和倒数k/4的数,比较后筛选掉,如此循环。

    终止条件:若本次迭代需要筛选掉t个数,而某个被筛选后的数组已经不足t/2个数,那么取该数组的末端数字与另一数组应该取到的数字进行比较,之后就很容易可以得到中位数。

    相关文章

      网友评论

          本文标题:【LeetCode】寻找两个已排序数组中的中位数

          本文链接:https://www.haomeiwen.com/subject/pthtdftx.html