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)).
Example 1:
nums1 = [1, 3]nums2 = [2]The median is 2.0
Example 2:
nums1 = [1, 2]nums2 = [3, 4]The median is (2 + 3)/2 = 2.5
题意理解:
给定任意两个已经排好序的数组, 要你求这两个数组的中位数. 并且时间复杂度不能大于O(log (m+n) )
思路历程:
1. 合并成一个数组, 再求其中位数. 于是想到了合并的算法(按思考的时间先后)
- 插入排序. 粗略一算, 时间复杂度为O(m*n).
- 二分插入. 粗略一算, 复杂度为 O(nlogm), (假设n<m)
可以看出要达到log(m+n)这个等级, 合并这条路走不通.
2. 逆推法. 假设成功合并了nums1(简称A,长度为n) 和nums2(简称B,长度为m), 得到一个数组C .通过观察C和它的中位数median可初步得到以下结论
- C.length = m + n
- 对于任意的 c1 ∈ C1, c2 ∈ C2 均有 c1 <= c2, 即 MAX(C1) <= MIN(C2)
- median可把M分成左半部分(C1), 和右半部分(C2). 并且C1.length == C2.length (或 C1.length == C2.length + 1, 将median放在C1)
中位数为 median = (MAX(C1) + MIN(C2)) /2 (m+n 为偶数) 或 MAX(C1) (m+n为奇数). (将median放在C1)
则任务转换为, 已知 A,B , 求满足上述条件的 MAX(C1),MIN(C2)
要满足条件1: 很容易满足....
要满足条件2: 由MAX(C1) <= MIN(C2) 可知
- MAX(C1中 来自A的元素) <= MIN(C2中 来自A的元素) (显然成立)
- MAX(C1中 来自A的元素) <= MIN(C2中 来自B的元素)
- MAX(C1中 来自B的元素) <= MIN(C2中 来自B的元素) (显然成立)
- MAX(C1中 来自B的元素) <= MIN(C2中 来自A的元素)
要满足条件3: C1.length == C2.length (或 C1.length == 1+ C2.length , 将median放在C2) , 设C1中 来自A的个数为x, 来自B的个数为y, 要满足
- C1.length = x + y , C2.length = m + n - x - y (或 m + n - x - y + 1)
即满足 y = (m + n + 1) /2 - x (利用除2向下取整,合并两种情况)
what?这个式子的意思就是 C1中 A的个数和B的个数满足线性关系, 这意味着啥?
这意味着 只要找到 x (C1中 A元素的数量) , 使得A,B 满足 条件2即可. 此话怎讲?
一个(x,y)的划分如图:
即满足:
- A[x-1] <= B[y]
- B[y-1] <= A[x]
临界值有 x =0, x = n , y = 0 , y = m(稍后讨论)
- 将x 从 0 到 n 进行顺序遍历, 这样复杂度为O(n)
- 从0到n 对x 进行二分查找, 这样复杂度为O(logn)
由此看来, 问题是可解决并且符合题目要求的.
得到初步得到算法:
var left = 0; var right = A.length; while(left <= right) { var x = (left + right) / 2; var y = (A.length + B.length + 1) / 2 - x; if(A[x-1] > B[y]) { //说明A[x-1]太大了. //如果 x增大, 则y会减少, 这样A[x-1]会更加比B[y]大. //所以 x应该减少. right = x; } else if(B[y-1] > A[x]) { //说明A[x]太小了 //如果 x减小,则 y会增大, 这样B[y-1]会比A[x]更大. //所以 x应该增大. left = x; } else { //说明x刚好满足条件2. var MAXA = A[x-1]; var MINB = B[y]; if((A.length + B.length )%2 == 0) { return (MAXA + MINB) / 2; } else{ return MAXA*1.0; } } }下面讨论 x=0 , x=n, y=0, y=m的情况 这四种情况, 对应的是
- C1中 A为空集 (导致A[x-1] 不存在)
- C2中 A为空集 (导致A[x]不存在)
- C1中 B为空集 (导致B[y-1]不存在)
- C2中 B为空集 (导致B[y]不存在)
若出现这四种, 将其视为满足条件
则有:
if (x !== 0 && y !== B.length && A[x - 1] > B[y]) { //说明A[x-1]太大了. //如果 x增大, 则y会减少, 这样A[x-1]会更加比B[y]大. //所以 x应该减少. right = x - 1;}else if (y !== 0 && x !== A.length && B[y - 1] > A[x]) { //说明A[x]太小了 //如果 x减小,则 y会增大, 这样B[y-1]会比A[x]更大. //所以 x应该增大. left = x + 1;}在获取最后结果的时候要也要判断: //说明x刚好满足条件2. if (x === 0) { var MAX_C1 = B[y - 1]; } else if (y === 0) { var MAX_C1 = A[x - 1]; } else { var MAX_C1 = A[x - 1] > B[y - 1] ? A[x - 1] : B[y - 1]; } if (x === A.length) { var MIN_C2 = B[y]; } else if (y === B.length) { var MIN_C2 = A[x]; } else { var MIN_C2 = A[x] > B[y] ? B[y] : A[x]; } if ((A.length + B.length) % 2 == 0) { return (MAX_C1 + MIN_C2) / 2; } else { return MAX_C1 * 1.0; } 以下为完整代码: /** * @param {number[]} A * @param {number[]} B * @return {number} */var findMedianSortedArrays = function (A, B) { //确保 A.length < B.length 实现 log(MIN(m,n)) if (A.length > B.length) { var temp = B; B = A; A = temp; } var left = 0; var right = A.length; while (left <= right) { var x = parseInt((left + right) / 2); var y = parseInt((A.length + B.length + 1) / 2) - x; if (x !== 0 && y !== B.length && A[x - 1] > B[y]) { //说明A[x-1]太大了. //如果 x增大, 则y会减少, 这样A[x-1]会更加比B[y]大. //所以 x应该减少. right = x - 1; } else if (y !== 0 && x !== A.length && B[y - 1] > A[x]) { //说明A[x]太小了 //如果 x减小,则 y会增大, 这样B[y-1]会比A[x]更大. //所以 x应该增大. left = x + 1; } else { //说明x刚好满足条件2. if (x === 0) { var MAX_C1 = B[y - 1]; } else if (y === 0) { var MAX_C1 = A[x - 1]; } else { var MAX_C1 = A[x - 1] > B[y - 1] ? A[x - 1] : B[y - 1]; } if (x === A.length) { var MIN_C2 = B[y]; } else if (y === B.length) { var MIN_C2 = A[x]; } else { var MIN_C2 = A[x] > B[y] ? B[y] : A[x]; } if ((A.length + B.length) % 2 == 0) { return (MAX_C1 + MIN_C2) / 2; } else { return MAX_C1 * 1.0; } } }};