題目
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)的算法舆吮。主要的思路是：
- 假設：第一個數(shù)組為A，長度為m乖坠；第二個數(shù)組為B薄榛，長度為n；AB合并排序好的數(shù)組為C（并沒有排序勒极，只是為了方便說明），長度為m+n虑鼎。
- 二分數(shù)組A辱匿，查找小于等于C[(m+n)/2+1]的最大的數(shù)所在的位置，二分中點的index為indexDim炫彩。
- 那么如何比較二分中點的數(shù)和C[(m+n)/2+1]的大小呢匾七，因為A,B均有序，所以看index就行了媒楼。就對于這個A[indexDim]乐尊，在B中二分查找小于等于A[indexDim]中最大的數(shù)所在的位置L戚丸。
- 然后我只需要比較L + indexDim + 1與（m+n）/2 + 1即可划址。
- 交換A扔嵌、B再來一次。
這個思想的問題在于代碼寫起來很麻煩夺颤，需要考慮奇數(shù)偶數(shù)的情況痢缎，特別是偶數(shù)時，還需要特殊處理(m+n)/2這個位置的數(shù)字世澜。所以我也交了幾次才AC了独旷。并且時間復雜度上也沒有O（log(m+n)）的算法優(yōu)。
-
因為最近剛開始學習JAVA寥裂，所以代碼質量比較低嵌洼。
// 二分第二個數(shù)組 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; } // 二分第一個數(shù)組 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; } /** * 尋找自己前一個的數(shù) * @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]; } } -
做完以后去看了一下別人的思路就是很常規(guī)的尋找第k小的問題：
- 當A[mid] < B[mid]時，第k小出現(xiàn)在（A_Right + B_Left）中封恰。
- 當A[mid] >= B[mid]時麻养，第k小出現(xiàn)在（A_Left + B_Right）中 。
- 并且通過（m+n+1）/2 和(m+n+2）/2的小技巧統(tǒng)一解決了奇數(shù)诺舔、偶數(shù)的問題鳖昌。
- 在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); }
