题目描述：
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m+n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例：
示例1：
nums1 = [1, 3] nums2 = [2] 则中位数是 2.0
示例2：
nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5
题目难度：困难
分析：
题目比较好理解，如果只看最后结果的话，很容易想到把两个数组合并，并且排序后就可以轻松的找到中位数，但这样不符合题目的意思，因为要求的时间复杂度为O(log(m+n))。这样一来不管你怎么合并排序都不可能达到题目要求，最好的也是O(nlogn)这个级别。代码如下：
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 定义一个大的数组用来存放两个小数组 int[] nums3 = new int[nums1.length + nums2.length]; // 分别把两个数组放在nums3里面 for (int i = 0; i < nums1.length; i++) { nums3[i] = nums1[i]; } for (int i = nums1.length, j = 0; i < nums3.length; i++, j++) { nums3[i] = nums2[j]; } // 对数组排序 Arrays.sort(nums3); // 对有序数组来说，只要根据数组的长度就可以轻松找到中位数。 return nums3.length % 2 == 0 ? (nums3[nums3.length / 2 - 1] + nums3[nums3.length / 2]) / 2.0 : nums3[nums3.length / 2]; } }
小结：
时间复杂度为O(nlogn)，这里为了省事，直接调用了API，虽不合法要求，但是结果是对的，执行速度较慢。
扩展：
根据题目的意思，是两个已经排好序的数组了，如果要合并的话，其实可以用二路归并排序，虽然时间复杂度也是O(nlogn)，但是前面的步骤都省略了，只需要最后的一个合并步骤即可，所以速度会快跟多，目前排名第一的代码如下（搬运）：
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int nums2length = nums2.length; // 定义一个大的数组用来存放两个小数组 int[] r = new int[nums1.length + nums2length]; int index = 0; int j = 0; /* 双层for循环，只要内层的元素小于外层的元素就把内层的元素放入数组中， 这样一来肯定会把nums2中所有小的元素放在最前面，直到找到一个比nums1中的元素 更大的，再把他放入即可，重复操作，即可以nums1中的元素和nums2中部分元素排序放好。 */ for (int num : nums1) { while (j < nums2length && num > nums2[j]) { r[index] = nums2[j]; j++; index++; } r[index] = num; index++; } // 这一步是把nums2中剩下的元素依次放入，因为前一个步骤中可能会因为 //nums2.length > nums1.length。导致nums2会漏掉后面的部分元素。 for (; j < nums2length; j++) { r[index] = nums2[j]; index++; } // 最后一步就是在排好序的数组中找到中位数即可。 int mi = r.length / 2; return r.length % 2 == 1 ? r[mi] : (r[mi - 1] + r[mi]) / 2.0; } }
小结：
此方法比较好理解，速度也快（不愧是排名第一的），巧妙的把两个排好序的数组放入一个大数组中，然后即可求出中位数。
总结：
简单的算法和想法不一定是慢的，有时候往往有奇效。
