题目难度：hard
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
翻译：
有两个已排序的数组nums1和nums2长度分别是m和n。
找到这两个数组的中值。整个运行时复杂度应该是O(log(m+n))。
想了老半天，
思路一：将两个数组直接放入List，然后调用Collection.sort()排好，最后返回其中位值
思路二：利用归并排序中的合并算法，将两个数组按顺序比大小拼接成一个数组（），最后返回其中位值
思路一Code：2080测试用例—107ms(beats 6.25%) 时间复杂度：O(N*logN)…………假设Collections.sort（）为快速排序O(N*logN)
1 public double findMedianSortedArrays(int[] nums1, int[] nums2) { 2 List<Integer> list = new ArrayList<Integer>(); 3 for (int i = 0; i < nums1.length; i++) { 4 list.add(nums1[i]); 5 } 6 for (int i = 0; i < nums2.length; i++) { 7 list.add(nums2[i]); 8 } 9 Collections.sort(list); 10 if ( list.size() % 2 == 0) { 11 return (list.get(list.size()/2) + list.get(list.size()/2 - 1))/2.0; 12 } else { 13 return list.get(list.size()/2); 14 } 15 }
用了Collection自带的sort方法，省得自己写排序代码。。。呃,有种作弊的感脚
总体速度貌似也还行，就是显得蠢了点=。=根本没用到“已排序”这个条件
【最近发现java.util.Arrays类直接就有Arrays.sort(int[] a)方法。。。】
思路二Code：2080测试用例—66ms(beats 70.29%) 时间复杂度：O(N+M)…………最小为O(N)
1 public static double findMedianSortedArrays2(int[] A, int[] B) { 2 int[] uniArray = uniSort(A, B); 3 if (uniArray.length % 2 == 0) { 4 return (uniArray[uniArray.length / 2] + uniArray[uniArray.length / 2 - 1]) / 2.0; 5 } else { 6 return uniArray[uniArray.length / 2]; 7 } 8 } 9 10 private static int[] uniSort(int[] A, int[] B) { 11 int[] result = new int[A.length + B.length]; 12 int i = 0,j = 0; 13 int k = 0; 14 15 while (i < A.length && j < B.length) { 16 if (A[i] < B[j]) { 17 result[k++] = A[i++]; 18 } else { 19 result[k++] = B[j++]; 20 } 21 } 22 while (i < A.length) { 23 result[k++] = A[i++]; 24 } 25 while (j < B.length) { 26 result[k++] = B[j++]; 27 } 28 return result; 29 }
这种方法应该是最容易想到的了，没啥技巧性可言，就是用一个辅助数组和一个int k 作为指针进行移动
代码可读性不错，时间复杂度也可观。
好吧，还是显得蠢了点。。。
参考答案（选了个可读性好点的）
思想：采用二分法，不考虑数值大小，只管查找当前下标是否在需要定位的下标的一半内
Code：2080测试用例—86ms(beats 21.34%) 时间复杂度：O(log(m + n))
1 public static double findMedianSortedArrays(int[] nums1, int[] nums2) { 2 // 处理无效边界 3 if (nums1 == null || nums2 == null) return 0.0; 4 5 int m = nums1.length, n = nums2.length; 6 if ((m + n) % 2 !=0) { 7 // 如果 m + n 长度是奇数，返回中间那一个 8 return getKth(nums1, 0, nums2, 0, (m + n + 1) / 2); 9 } else { 10 // 如果 m + n 长度是偶数，两个函数将返回一个左数和一个右数 11 return (getKth(nums1, 0, nums2, 0, (m + n + 1) / 2) + getKth(nums1, 0, nums2, 0, (m + n + 2) / 2)) / 2.0; 12 } 13 } 14 15 private static double getKth(int[] nums1, int start1, int[] nums2, int start2, int k) { 16 // 这个函数旨在nums1+nums2中找到第k个元素[而不是下标为k，这两个数组并没有合并不存在统一下标] 17 18 // 如果nums1耗尽，则返回nums2中的kth号 19 if (start1 > nums1.length - 1) return nums2[start2 + k - 1]; 20 21 // 如果nums2耗尽，则返回nums1中的第k号 22 if (start2 > nums2.length - 1) return nums1[start1 + k - 1]; 23 24 // 如果k==1，返回第一个数字 25 // 因为nums1和nums2是排序的，所以nums1和nums2的起始点中的较小的一个是第一个 26 if (k == 1) return Math.min(nums1[start1], nums2[start2]); 27 28 int mid1 = Integer.MAX_VALUE; 29 int mid2 = Integer.MAX_VALUE; 30 // 为什么不取0，因为当某一边长度不够折半时，它的mid默认长度应该比任何能折半的mid都大（保证让对方折半） 31 if (start1 + k / 2 - 1 < nums1.length) mid1 = nums1[start1 + k / 2 - 1]; 32 if (start2 + k / 2 - 1 < nums2.length) mid2 = nums2[start2 + k / 2 - 1]; 33 34 // 将数组中的一半从nums1或nums2中删除。把k切成两半 35 if (mid1 < mid2) { 36 return getKth(nums1, start1 + k / 2, nums2, start2, k - k / 2); //nums1.right + nums2 37 } else { 38 return getKth(nums1, start1, nums2, start2 + k / 2, k - k / 2); //nums1 + nums2.right 39 } 40 }
看了老半天才勉强看懂，比较难理解，不过时间复杂度小。
下面举个例子方便理解：
A【。。。】数组
B【。。。】数组
很假设中位数下标为k
下面以这俩数组为例，介绍这个“二分法求俩已排序数组中位数”
1. k =( n + m +1) / 2 // 假设m+n是奇数
2. 假设合并后的数组为C【。。。】，现在将C平均分成4部分，所以可以分为
C【0，k/2-1】;// k/2-1前半段的中位数的下标
C【略1】
C【略2】
C【略3】
3. 现在假如A内可以数到下标 k/2-1 = 1，B也可以数到。
所以C的k点的值必然大于 A数组k/2 与 B数组k/2 这两点中小的那一个点！所以小的那一个点对应的数组从起点到此点都不可能出现k，所以可以删去。
所以比较 A数组k/2 与 B数组k/2 ，将小的那个数组从start到k/2截去(将起点设置为start+k/2-1),然后继续递归搜索。
总结：如果真的出了这种题目，笔试就写第二种吧，复杂度也差不太多。面试的话先说第二种，再说第三种。
ps：LeetCode中写注释貌似会影响最后的成绩。