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
这道题,位于整个题目的,第四题,原本以为是一道水题,就是在做的过程中注意一下边界条件的处理就可以了的题呢,但是当我看到需要考虑时间复杂度的时候,我瞬间就蒙了,因为时间复杂度要求是log级别的,就是相当于告诉我们,不能把两个数组直接合并成一个数组了。所以,这题的难度一下子就上来了,后来查了点资料,先把答案晒出来吧,然后再慢慢解释,为什么要这么做:
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int total = nums1.length+nums2.length;
if(total%2==0){
return (findKth(total/2+1, nums1, nums2, 0, 0)+findKth(total/2, nums1, nums2, 0, 0))/2.0;
}else{
return findKth(total/2+1, nums1, nums2, 0, 0);
}
}
public int findKth(int k, int[] nums1, int[] nums2, int s1, int s2){
if(s1>=nums1.length)
return nums2[s2+k-1];
if(s2>=nums2.length)
return nums1[s1+k-1];
if(k==1)
return Math.min(nums1[s1], nums2[s2]);
int m1 = s1+k/2-1;
int m2 = s2+k/2-1;
int mid1 = m1<nums1.length?nums1[m1]:Integer.MAX_VALUE;
int mid2 = m2<nums2.length?nums2[m2]:Integer.MAX_VALUE;
if(mid1<mid2){
return findKth(k-k/2, nums1, nums2, m1+1, s2);
}else{
return findKth(k-k/2, nums1, nums2, s1, m2+1);
}
}
}
好了,整个答案就是这个样子的,其实这个问题,我们是可以把它进行转换的,我说一下转换的步骤,大家就应该明白了。
1.找一个数组中最大数和最小数的问题,最笨的方法是,先排序,然后返回最大值,最小值。
2.稍微优化一点的算法就是一个循环下来扫描,采用动态规划的算法,将最大值,最小值求出来。
3.可以采用建堆的方式,说到这想必大家应该能明白了,就是建立一个大根堆,或者一个小根堆,然后从找找到相应位置的东西即可。
4.我们采用的是第四种,是一个类似于快排的方式,每次我们都随机将一组数分成两个部分,然后采用同样的方法,每次都可以随机的丢弃数列中的一部分,这样之后我们就可以舍弃很多数据了。
然后我们这个题,采用的就是大概第四种方法:
思想大概就是上面这种方式,每次都可以舍弃很大的一个部分。然后采用递归的方式。