题目
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
思路
-
先说我的解题思路（太久没做题了，思路很怪）。我写了一个O(2*logm*logn)的算法。主要的思路是：
- 假设：第一个数组为A，长度为m；第二个数组为B，长度为n；AB合并排序好的数组为C（并没有排序，只是为了方便说明），长度为m+n。
- 二分数组A，查找小于等于C[(m+n)/2+1]的最大的数所在的位置，二分中点的index为indexDim。
- 那么如何比较二分中点的数和C[(m+n)/2+1]的大小呢，因为A,B均有序，所以看index就行了。就对于这个A[indexDim]，在B中二分查找小于等于A[indexDim]中最大的数所在的位置L。
- 然后我只需要比较L + indexDim + 1与（m+n）/2 + 1即可。
- 交换A、B再来一次。
这个思想的问题在于代码写起来很麻烦，需要考虑奇数偶数的情况，特别是偶数时，还需要特殊处理(m+n)/2这个位置的数字。所以我也交了几次才AC了。并且时间复杂度上也没有O（log(m+n)）的算法优。
-
因为最近刚开始学习JAVA，所以代码质量比较低。
// 二分第二个数组 public int binarySearchTwo(int[] arr, int target, int flag) { int l = 0, r = arr.length - 1; if (l == r) { return arr[l] > target ? -1 : 0; } while (l < r) { int dim = (l + r) / 2 + 1; if ((arr[dim] < target && flag == 0) || (arr[dim] <= target && flag == 1)) { l = dim; } else { r = dim - 1; } } return (arr[l] < target && flag == 0) || (arr[l] <= target && flag == 1) ? l : -1; } // 二分第一个数组 public int binarySearchOne(int[] nums1, int[] nums2, int flag) { int l = 0, r = nums1.length - 1, m = nums1.length + nums2.length; while (l < r) { int dim = (l + r) / 2 + 1; int b = this.binarySearchTwo(nums2, nums1[dim], flag) + 1; if (dim + b <= m / 2) { l = dim; } else { r = dim - 1; } } return l; } /** * 寻找自己前一个的数 * @param indexOne * @param indexTwo * @return */ public int maxNext(int[] num1, int[] num2, int indexOne, int indexTwo) { int resOne = indexOne == 0 ? -10000 : num1[indexOne - 1]; int resTwo = indexTwo == -1 ? -10000 : num2[indexTwo]; return Math.max(resOne, resTwo); } public double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.length == 0) { return nums2.length % 2 == 0 ? (nums2[nums2.length / 2 - 1] + nums2[nums2.length / 2]) / 2.0 : (nums2[nums2.length / 2]); } else if (nums2.length == 0) { return nums1.length % 2 == 0 ? (nums1[nums1.length / 2 - 1] + nums1[nums1.length / 2]) / 2.0 : (nums1[nums1.length / 2]); } int m = nums1.length + nums2.length; int indexOne = binarySearchOne(nums1, nums2, 0); int bOne = binarySearchTwo(nums2, nums1[indexOne], 0); int firstOne = maxNext(nums1, nums2, indexOne, bOne); int indexOneSum = indexOne + bOne + 2; int indexTwo = binarySearchOne(nums2, nums1, 1); int bTwo = binarySearchTwo(nums1, nums2[indexTwo], 1); int firstTwo = maxNext(nums2, nums1, indexTwo, bTwo); if (m % 2 == 0) { return indexOneSum == m / 2 + 1 ? (nums1[indexOne] + firstOne) / 2.0 : (nums2[indexTwo] + firstTwo) / 2.0; } else { return indexOneSum == m / 2 + 1 ? nums1[indexOne] : nums2[indexTwo]; } } -
做完以后去看了一下别人的思路就是很常规的寻找第k小的问题：
- 当A[mid] < B[mid]时，第k小出现在（A_Right + B_Left）中。
- 当A[mid] >= B[mid]时，第k小出现在（A_Left + B_Right）中 。
- 并且通过（m+n+1）/2 和(m+n+2）/2的小技巧统一解决了奇数、偶数的问题。
- 在LeetCode上两种方法跑下来时间是差不多的~
public double findMedianSortedArrays(int[] A, int[] B) { int m = A.length, n = B.length; int l = (m + n + 1) / 2; int r = (m + n + 2) / 2; return (getKMin(A, 0, B, 0, l) + getKMin(A, 0, B, 0, r)) / 2.0; } public double getKMin(int[] A, int Astart, int[] B, int Bstart, int k) { if (Astart > A.length - 1) return B[Bstart + k - 1]; if (Bstart > B.length - 1) return A[Astart + k - 1]; if (k == 1) return Math.min(A[Astart], B[Bstart]); int Amin = Integer.MAX_VALUE, Bmin = Integer.MAX_VALUE; if (Astart + k / 2 - 1 < A.length) Amin = A[Astart + k / 2 - 1]; if (Bstart + k / 2 - 1 < B.length) Bmin = B[Bstart + k / 2 - 1]; return Amin < Bmin ? getKMin(A, Astart + k / 2, B, Bstart, k - k / 2) : getKMin(A, Astart, B, Bstart + k / 2, k - k / 2); }
