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.我们采用的是第四种，是一个类似于快排的方式，每次我们都随机将一组数分成两个部分，然后采用同样的方法，每次都可以随机的丢弃数列中的一部分，这样之后我们就可以舍弃很多数据了。
然后我们这个题，采用的就是大概第四种方法：
思想大概就是上面这种方式，每次都可以舍弃很大的一个部分。然后采用递归的方式。
