4. Median of Two Sorted Arrays(hard)

02-12

題目：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(nlogn)，所以還是另想辦法。

這個問題的關鍵是找到中位數，而中位數並不需要合併才能找到。

可以設置兩個數組的索引i和j，往後遍歷，當i+j的總值達到(nums1.size()+nums2.size())/2時停止遍歷返回合適值即可。

我嘗試了一下這種方法，方法本身實現不難，但是遇到了很多的邊界問題和細節問題，寫起來很費勁，且複雜度為O(m+n)，還是放棄了。

嘗試一下其他方法：

方法1：

中位數問題實際上是一個尋找第(m+n)/2小的數的問題，也就是一個尋找第k小數的問題。

首先假設數組A和B的元素個數都大於k/2，我們比較A[k/2-1]和B[k/2-1]兩個元素，這兩個元素分別表示A的第k/2小的元素和B的第k/2小的元素。這兩個元素比較共有三種情況：>、<和=。如果A[k/2-1]<B[k/2-1]，這表示A[0]到A[k/2-1]的元素都在A和B合併之後的前k小的元素中。換句話說，A[k/2-1]不可能大於兩數組合併之後的第k小值，所以我們可以將其拋棄。

通過遞歸，查找第k小的數，每次都拋棄一部分。

double findKth(int a[], int m, int b[], int n, int k) { //always assume that m is equal or smaller than n if (m > n) return findKth(b, n, a, m, k); if (m == 0) return b[k - 1]; if (k == 1) return min(a[0], b[0]); //divide k into two parts int pa = min(k / 2, m), pb = k - pa; if (a[pa - 1] < b[pb - 1]) return findKth(a + pa, m - pa, b, n, k - pa); else if (a[pa - 1] > b[pb - 1]) return findKth(a, m, b + pb, n - pb, k - pb); else return a[pa - 1]; } class Solution { public: double findMedianSortedArrays(int A[], int m, int B[], int n) { int total = m + n; if (total & 0x1) return findKth(A, m, B, n, total / 2 + 1); else return (findKth(A, m, B, n, total / 2) + findKth(A, m, B, n, total / 2 + 1)) / 2; } };