LeetCode第4题:Median of Two Sorted Arrays总结

题目

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

大意

有两个排好序的数组nums1和nums2,分别长m和n.找出两个数列的中值,复杂度应该为O(log (m+n)).

思路

这道题虽然知道应该是分治的思路,我没有做出来,找了一下discuss里面的题解,看了一下,打算把有关的分治书上好好看过之后在回顾之后再更新下这道题
这里贴出discuss的两个帖子链接,这两个是discuss里面顶的最多了两篇。第一篇思路比较正常,翻译了下。第二篇的思路更是很巧妙的避开了奇偶数的讨论,但不知道是否具有普适性。

Python:

我的错误代码如下:(仅作纪念)

参考

原文:《share my o(log(min(m,n)) solution with explanation

翻译

  • 已知一个长度为m的数组A,我们可以把它拆分成两部分:

右边的所有元素都比左边的元素大。
左边有i个元素,右边有m – 1个元素。
一共可以有m+1中拆分的办法。(i = 0 ~ m)
i = 0时,左半部分有0个元素,右半部份有m个元素;
i = m时,左半部分有m个元素,右半部份有0个元素。

  • 对于数组B,我们可以同理拆成:

左边有k个元素,右边有n-j个元素。

  • 将A的左边和B的左边放到同一个集合中(取名”LeftSet”)
    将A的右边和B的右边放到同一个集合中(取名”RightSet”)

  • 如果我们能够保证:

那么我们就已经把{A, B}中所有的元素,分成了长度相等的两个部分,并且其中一部分的元素总是比另一部分的元素大。这样的话,中值(median)就能较容易地找到了

  • 为了保证这两点,我们只需要保证:

  • 所以,我们要去做的就是:
    取i从0到m,找出符合上述两点要求的i值ix和对应的j值jx

  • 我们可以用二分查找来找出它,怎么做呢?
    1) 如果 B[j0 – 1] > A[i0],那么”ix” 就肯定不在[0, i0]中,为什么呢?
    因为如果 ix < i0, 那么jx = (m + n + 1) / 2 -ix > j0, 那么 B[jx -1] >= B[j0 – 1] > A[i0] >= A[ix],这和条件2是有冲突的!所以ix是不能比i0小的。
    2) 如果 A[i0 – 1] > B[j0],那么”ix”就肯定不在[i0, m]中。
    (证明同上)

  • 所以我们就可以按下边的步骤进行二分搜索:
    1) 设置 imin, imax = 0, m,然后开始在[imin, imax]中搜索
    2) i = (imin + imax) / 2; j = (m + n +1) / 2 - i
    3) if B[j – 1] > A[i]: 在[i + 1, imax]中继续搜索;
    elif A[i – 1] > B[j]: 在[imin, i – 1]中继续搜索;
    else: bingo!这就是我们要找的i了!

  • 当我们找到ix时,中值(median)就是:

或:

  • 代码如下:(Python)

C++

参考
(《Very concise O(log(min(M,N))) iterative solution with detailed explanation》的代码)

发表评论

电子邮件地址不会被公开。 必填项已用*标注