题目参上,以下是解题思路:
首先,我们应该想到的一种方法是把两数组合并为一个整体的数组,然后返回其中位数即可。那么我们如何合并两数组呢?我们可以用归并排序,设置上下两指针,不断遍历返回较小的那个同时指针后移,这样我们就可以把数组合并,同时我们要注意这样的几种特殊情况:
1.nums1和nums2中有空数组
显然,若其中一个为空,我们直接判断另一个的中位数即可。
2.nums1和nums2的长度不一样
这种怎么办呢?我们只需要设置进入数组的长度即可,即若其中一个已经全部进入数组,那么直接把另一个数组的剩余所有数全进入即可。
那么这个思路能否优化一下呢?
首先,我们要注意,我们只是想要找这两数组的中位数,其实并不需要把整个的数组全都和起来,我们只需要找到数组的中位数所在的位置即可,其次,我们的搜寻方法能否优化呢?显然,二分查找就在这里派上了用场。
下面是解题思路:( 作者:windliang 来源:力扣(LeetCode))
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n1 = nums1.length ;
int n2 = nums2.length ;
int left = ( n1 + n2 + 1 ) / 2 ;
int right = ( n1 + n2 + 2 ) /2 ;
return (erFen( nums1 , 0 , n1 - 1 , nums2 , 0 , n2 - 1 , left ) + erFen(nums1 , 0 , n1 - 1 , nums2 , 0 , n2 - 1 , right )) * 0.5 ;//注意不能用 /2
}
private int erFen(int[] nums1 , int start1 , int end1 , int[] nums2 , int start2 , int end2 , int key){
int len1 = end1 - start1 + 1 ;
int len2 = end2 - start2 + 1 ;//注意是实时长度更新
if( len1 > len2 ){
return erFen(nums2 , start2 , end2 , nums1 , start1 , end1 , key) ;//保证len1小于len2,这样如果出现空数组则一定为len1
}
if( len1 == 0 ){
return nums2[start2 + key - 1] ;//注意数组是从0开始的
}
if( key == 1){
return Math.min(nums1[start1] , nums2[start2]) ;
}
int i = start1 + Math.min(len1 , key / 2 ) - 1 ;
int j = start2 + Math.min(len2 , key / 2 ) - 1 ;//找到两标记位置i和j
if(nums1[ i ] > nums2[ j ]){
return erFen(nums1 , start1 , end1 , nums2 , j + 1 , end2 , key - ( j - start2 + 1)) ;
}
else{
return erFen(nums1 , i + 1 , end1 , nums2 , start2 , end2 , key - ( i - start1 + 1)) ;
}
}
}