【leetcode】medianofTwoSortedArrays

leetcode真是博大精深，难度为5的题真不是盖的，高人层出不穷, 下面直接学习一下网友huoyao的 方法

这是leetcode的第4题, 题干如下

1. There are two sorted arrays A and B of size m and n respectively. 2. Find the median of the two sorted arrays. 3. The overall run time complexity should be O(log (m+n)).

leetcode给出的 tag 如下

Divide and Conquer Array Binary Search

简单翻译一下, 就是给出两个有序数组, 讲述组合并以后, 求出中位数。

中位数将一个数组分为数目相同的两半，数组长度为奇数， 那么中位数下标为 n/2+1, 长度为偶数的话, 中位数为 (n/2+1 + n/2-1)/2

要求算法的时间复杂度为O(log (m+n))

废话不多说，huoyao的算法如下

给定一个排好序的数组A, 长度为m, 可以划分为如下两个部分

{ A[0], A[1], ... , A[i - 1] } | { A[i], A[i + 1], ... , A[m - 1] }

左边的所有元素都小于右边的元素

左边有 i 个元素, 右边有 m-i 个元素

总共有 m+1 中划分方式(i = 0 ~ m)

当 i=0 , 左边有 0 个元素, 右边有 m 个元素

当 i=m , 左边有 m 个元素, 右边有 0 个元素

对于B数组, 也可以类似的划分

{ B[0], B[1], ... , B[j - 1] } | { B[j], B[j + 1], ... , B[n - 1] }

将A的左边与B的左边放到同一个集合中(取名 左部)

将A的右边与B的右边放到同一个集合中(取名 右部)

         LeftPart              |            RightPart { A[0], A[1], ... , A[i - 1] } | { A[i], A[i + 1], ... , A[m - 1] }{ B[0], B[1], ... , B[j - 1] } | { B[j], B[j + 1], ... , B[n - 1] }

如果我们可以保证

1. 左部的长度 = 右部的长度 (或者左部的长度 = 右部的长度+1)2. 右部的所有元素都大于左部

那么我们已经将{A,B}中的元素划分为左右两个相同的部分, 中位数很容易就找到了

用算法的方式表示以上的条件, 如下

(1) i + j == m - i + n - j (or: m - i + n - j + 1)     if n >= m, we just need to set:            i = 0 ~ m, j = (m + n + 1) / 2 - i (2) B[j - 1] <= A[i] and A[i - 1] <= B[j]     considering edge values, we need to ensure:           (j == 0 or i == m or B[j - 1] <= A[i]) and                (i == 0 or j == n or A[i - 1] <= B[j])

至此, 算法变为

 Search i from 0 to m, to find an object "i" to meet condition (1) and (2) above.

现在开始引入 二分查找

循环遍历中, 当前的循环值为i0, j0, 若i0,j0是需要的解, 那么他们满足上述条件, 否则, 与条件相违背, 则有

B[j0 - 1] > A[i0] 或者 A[i0 - 1] > B[j0],

如果B[j0 - 1] > A[i0], 那么 "ix" 不可能在 [0, i0]之中, why? :

因为如果 ix < i0, 那么jx = (m+n+1)/2-ix > j0,那么  B[jx - 1] >= B[j0 - 1] > A[i0] >= A[ix]而这个违反了 condition (2), ix 肯定不是解, 所以ix 不可能比i0小

同样的 ,如果 A[i0 - 1] > B[j0] , ix" 不可能在 [i0, m] 之中

所以算法进一步推算为:

1. set imin, imax = 0, m, then start searching in [imin, imax]2. i = (imin + imax) / 2; j = (m + n + 1) / 2 - i3. if B[j - 1] > A[i]: continue searching in [i + 1, imax]   elif A[i - 1] > B[j]: continue searching in [imin, i - 1]   else: bingo! this is our object "i"

以下是原作者的python代码

def Median2(A, B):    m, n = len(A), len(B)    if m > n:        return Median2(B, A)    imin, imax = 0, m    while imin <= imax:        i = (imin + imax) / 2        j = (m + n + 1) / 2 - i        if j > 0 and i < m and B[j - 1] > A[i]:            imin = i + 1        elif i > 0 and j < n and A[i - 1] > B[j]:            imax = i - 1        else:            if i == 0:                num1 = B[j - 1]            elif j == 0:                num1 = A[i - 1]            else:                num1 = max(A[i - 1], B[j - 1])            if (m + n) & 1:                return num1            if i == m:                num2 = B[j]            elif j == n:                num2 = A[i]            else:                num2 = min(A[i], B[j])            return (num1 + num2) / 2.0

以下是个人的一些难点解释

学习本就是一个痛苦的过程, 但是每有会意, 便欣然忘食, 也是一种快乐

1. 中位数的概念

2. 分治算法

3. 二分查找的引入, 原文说的不是十分好理解, 翻译的时候用红色的字体标示了

4. 运算时必须保证A数组长度小于B： i和j, 将AB两个数组划分为长度相同的两个集合, 如果A数组非常长, 那么i在划分中可能出现 len(A的右部加上B的全部) < len(A的左部) 的情况， 此时，j计算值为负。

5. 边界值理解：

            LeftPart              |            RightPart { A[0], A[1], ... , A[i - 1] } | { A[i], A[i + 1], ... , A[m - 1] }{ B[0], B[1], ... , B[j - 1] } | { B[j], B[j + 1], ... , B[n - 1] }判断B[j-1] 是否小于 A[i]时候, 需要保证 j > 0 并且 i < mj > 0 理解: j如果等于0的话, 其实B组整个就划分为 RightPart了i < m 理解: i如果等于m的话, 其实A组整个就划分为 LeftPart了判断A[i - 1] 是否小于 B[j] 时候, 同样的, 需要保证 i > 0 并且 j < n 

6. java版本的实现, 有狗尾续貂之嫌

    public double findMedianSortedArrays(int A[], int B[]) {        int m = A.length;        int n = B.length;// 这里必须保证A长度小于B// 理解: i和j, 将AB两个数组划分为长度相同的两个集合, 如果A数组非常长, 那么i在划分中可能出现         // len(A的右部加上B的全部) < len(A的左部)// 的情况， 此时，j计算值为负。         if (m > n) {            return findMedianSortedArrays(B, A);        }        int imin = 0;        int imax = m;        int num1 = 0, i = 0, j = 0, num2 = 0;        while (imin <= imax) {            i = (imin + imax) / 2;            j = (m + n + 1) / 2 - i;// 边界值需要保证            if (j > 0 && i < m && B[j - 1] > A[i]) {                imin = i + 1;            } else if (i > 0 && j < n && A[i - 1] > B[j]) {                imax = i - 1;            } else {                if (i == 0) {                    num1 = B[j - 1];                } else if (j == 0) {                    num1 = A[i - 1];                } else {                    num1 = Math.max(A[i - 1], B[j - 1]);                }                break;            }        }        if ((m + n) % 2 == 1) {            return num1;        }        if (i == m) {            num2 = B[j];        } else if (j == n) {            num2 = A[i];        } else {            num2 = Math.min(A[i], B[j]);        }        return (num1 + num2) / 2.0;    }