4. Median of Two Sorted Arrays (hard)
给定两个有序数组,找中位数median,按照自己的思路AC了,用了挺长时间
需要学习基础算法
4.1.png
- 心得:
- 解题要形成自己的框架!
- 考虑索引在数组中是否有效,同时也要考虑索引的实际含义
- 对两个需要同时成立的大小约束A[i-1]<B[j],B[j-1]<A[i]分开判断,也就是用两个if
- 需要对所有的情况判断是否满足约束,不满足的话要进行修改;满足条件后需要对所有的情况进行相应形式的return
- 其实吧,如果对这两个数组进行归并排序(一次就行),可以直接算出median,因为m+n为奇数时median就是索引为(m+n+1)/2-1的元素,m+n为偶数时median就是索引为(m+n)/2-1和(m+n)/2两个元素的均值,但是时间复杂度为O(m+n),高于O(log(m+n))的要求,因为不需要对全部元素排序就能找出median!
- 中位数把一串数分成等长的两部分,并且这两部分有大小关系,根据中位数的这两个性质建模
- 大小约束:给定的两个数组为A,B(长度分别为m,n),将A切割成左右两部分,将B切割成左右两部分,再把AB的左边部分看作整体,把AB的右边部分看作整体,需要满足max(left_part)≤min(right_part).假设切割位置分别为i,j,因为AB有序,所以只需要满足A[i-1]<B[j],B[j-1]<A[i]即可(i,j为切割位置,表示右边部分第一个元素的索引).
- 等长约束:当m+n为偶数时:len(left_part)==len(right_part)或者当m+n为奇数时len(left_part)==len(right_part)+1,奇数时这样定义相当于把median放在左边部分
- 如何衡量len()?可以通过切割位置实现,以数组A为例,把A切开,m个元素共有m + 1个切割位置i,i取值从0到m.下图中的↑符号就是切割位置
4.2.png
切割位置代表了切割后左边元素的个数,同时也是切割后右边第一个元素的索引,所以在使用切割位置时要明确使用的是哪种实际含义. - 有了len(),具体实现len(left_part)==len(right_part)和len(left_part)==len(right_part)+1这两个约束:
- 当m + n为odd(奇数)时,有i + j = m - i + n - j + 1.化简后得到i,j之间的关系,j = (m + n + 1)/2 - i
- 当m + n为even(偶数)时,可以均分成两份,有i + j = m - i + n - j.此时median是中间两个数的平均值,这两个数的位置是left = (m + n)/2和right = left + 1,所以它们的索引是left - 1 和 right - 1.一个在左边部分,一个在右边部分,化简后得到i,j之间的关系,j = (m + n)/2 - i.
这里要注意,在计算机中,对于int整型运算,结果只保留正数部分,所以有(m + n)/2 = (m + n + 1)/2 - i,这样就把奇数情况和偶数情况中i,j的等式关系统一起来了,即j = (m + n + 1)/2 - i,这在后面讨论取值范围时也用到了,非常重要!
- 至此,约束已经实现了,还剩下最后一步:寻找满足条件的切割位置i,有了i通过j = (m + n + 1)/2 - i得到j,因为时间复杂度要求是O(log(m+n)),所以采用二分法
-
最后的最后说一下约束条件划分
4.3.png
class Solution{
public double findMedianSortedArrays(int[] A, int[] B){
int m = A.length;
int n = B.length;
//1.如果m>n则调换数组顺序,使满足m≤n,对长度短的数组做二分,速度更快!
if(m>n) return findMedianSortedArrays(B, A);
//2.(边界)当A为空时找出B中的median即可,分奇偶讨论
//没有A,B都为空的情况
if (m == 0 && n%2==1) return B[(n+1)/2-1];
if(m == 0 && n%2==0) return (B[n/2-1]+B[n/2])/2.0;
int iMin = 0,iMax = m,p = (m+n+1)/2;// p是partial,代表i,j等式中固定不变的成分
//3.通过循环实现二分法,时间复杂度是O(log(m+n))
while(iMin <= iMax){
int i = (iMin + iMax)/2;
int j = p - i;
//4.两个大小关系约束分别处理,会发现可以合并成两行
//4.1 0<i<m时0<j<n或i==0时,0<j<n 此时B[j-1] A[i]都有意义
if(((i>0 && i< m) ||i == 0) && B[j-1] > A[i]) iMin += 1;
//4.2 0<i<m时0<j<n或i==m时j>0(j肯定小于n,因为j==n会导致只有左边部分)
else if (((i>0 && i< m)||i == m) && A[i-1] > B[j]) iMax -= 1;
//6. 进入到else说明对于0≤i≤m有B[j-1] < A[i] && A[i-1] < B[j],找出median即可
else {
// i==0
if (i == 0 && j == n && m == n) return (A[0] + B[n - 1]) / 2.0;
else if (i == 0 && j == n && m + 1 == n) return B[n - 1];
else if (i == 0 && j < n && (m + n) % 2 == 1) return B[j - 1];
else if (i == 0 && j < n && (m + n) % 2 == 0) return ( B[j-1]+Math.min(A[0], B[j])) / 2.0;
// i == m
else if (i == m && j == 0) return (A[m - 1] + B[0]) / 2.0;
else if (i == m && (m + n) % 2 == 1) return Math.max(A[m - 1], B[j - 1]);
else if (i == m &&(m + n) % 2 == 0) return (Math.max(A[m - 1], B[j - 1]) + B[j]) / 2.0;
// 0 < i < m
else if ((m + n) % 2 == 1) return Math.max(A[i - 1], B[j - 1]);
else return (Math.max(A[i - 1], B[j - 1]) + Math.min(A[i], B[j])) / 2.0;
}
}
//double函数的返回值,其实这里写任何double的数都可以,因为用不到
return 0.0;
}
}
