【leetcode】medianofTwoSortedArrays

王朝学院·作者佚名  2016-05-28
窄屏简体版  字體: 小  |  中  |  大  |  超大  

【leetcode】medianofTwoSortedArraysleetcode真是博大精深,难度为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

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

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

中位数的概念分治算法

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

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

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

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; }

 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
© 2005- 王朝網路 版權所有 導航