今天是一道面試中比較常見的算法題，來自leetcode，難度為hard，Acceptance為38.2%。
題目如下
給定兩個大小為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2。
請你找出這兩個正序數(shù)組的中位數(shù)，并且要求算法的時間復(fù)雜度為 O(log(m + n))。
你可以假設(shè) nums1 和 nums2 不會同時為空。示例 1:
nums1 = [1, 3]
nums2 = [2]
則中位數(shù)是 2.0示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
則中位數(shù)是 (2 + 3)/2 = 2.5來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
回復(fù)0000查看更多題目
解題思路
思路一
初看這道題，尋找中位數(shù)，在一個有序數(shù)組中尋找一個數(shù)第一個想到的當(dāng)然是二分查找，可以做到O(logn)是時間復(fù)雜度。那個對于兩個有序數(shù)組怎么處理呢？
第一個想到的就是將兩個數(shù)組合并成一個有序數(shù)組，這樣就可以直接取合并后數(shù)組的第len+1 / 2個值(長度是奇數(shù))或者是第len+1 / 2和len+1 / 2 - 1的平均值(長度是偶數(shù))；
而合并兩個有序數(shù)組，顯然是歸并排序的一個步驟，時間復(fù)雜度是O(m+n)。思路有了，代碼如下
代碼如下
Java版
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] nums;
int m = nums1.length;
int n = nums2.length;
nums = new int[m + n];
if (m == 0) {
if (n % 2 == 0) {
return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
} else {
return nums2[n / 2];
}
}
if (n == 0) {
if (m % 2 == 0) {
return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
} else {
return nums1[m / 2];
}
}
int count = 0;
int i = 0, j = 0;
while (count != (m + n)) {
if (i == m) {
while (j != n) {
nums[count++] = nums2[j++];
}
break;
}
if (j == n) {
while (i != m) {
nums[count++] = nums1[i++];
}
break;
}
if (nums1[i] < nums2[j]) {
nums[count++] = nums1[i++];
} else {
nums[count++] = nums2[j++];
}
}
if (count % 2 == 0) {
return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
} else {
return nums[count / 2];
}
}
因為涉及到了歸并排序的一步，所以其時間復(fù)雜度是O(m+n)
空間復(fù)雜度：因為在合并數(shù)組時開辟了一個數(shù)組，保存合并后的兩個數(shù)組 O(m+n)
思路二
在上面的步驟中，我們先合并兩個數(shù)組，然后再取中間的值。其實仔細想一下的話就會發(fā)現(xiàn)，我們并不需要將兩個數(shù)組真的合并，只需要知道合并后中位數(shù)在哪個數(shù)組的哪個位置就可以了。
因為在合并兩個數(shù)組之前，已經(jīng)知道了兩個數(shù)組的長度m，n，也就知道了合并后的長度len=m+n。
這樣我們在合并兩個數(shù)組的時候（不需要真的開辟一塊存儲空間保持合并的數(shù)組，只需要按歸并的邏輯遍歷兩個數(shù)組），就可以在訪問到len+1 / 2的元素時停止就可以了。這也就是我們要的值。
當(dāng)然仍然需要注意奇偶數(shù)的區(qū)別，長度是奇數(shù)是第len/2個值，長度是偶數(shù)是第len+1 /2和len+1 / 2 - 1的平均值。
代碼如下
Java版
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
int len = m + n;
int left = -1, right = -1;
int aStart = 0, bStart = 0;
for (int i = 0; i <= len / 2; i++) {
left = right;
if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
right = A[aStart++];
} else {
right = B[bStart++];
}
}
if ((len & 1) == 0)
return (left + right) / 2.0;
else
return right;
}
時間復(fù)雜度分析，因為從頭遍歷到len+1 / 2，len=m+n，所以時間復(fù)雜度依舊是 O(m+n)。
空間復(fù)雜度上，因為我們申不需要真的開辟一塊存儲空間保持合并的數(shù)組，只需要存儲aStart，bStart等幾個記錄位置的值。所以空間復(fù)雜度是 O(1)。
思路三
上邊的兩種解題思路，時間復(fù)雜度都是O(m+n)，都達不到題目的要求 O(log(m+n)。看到 時間復(fù)雜度是log，很明顯，我們又回到一開始說的用二分查找的思路解決問題。題目是要求中位數(shù)，可以將其看成是求合并后第 k 小數(shù)的一種特殊情況，而求第 k 小數(shù)是可以做到時間復(fù)雜度O(log(m+n)的。
在上面的思路二中，我們一次遍歷就相當(dāng)于去掉一個不是中位數(shù)的值，而兩個數(shù)組都是有序的，其實我們完全可以按照二分查找的思路，一次遍歷去掉一半兒不是中位數(shù)的值。即，設(shè)我們要找的中位數(shù)是第 k 小數(shù)，我們可以每次循環(huán)排除掉 k/2 個數(shù)。
例：
假設(shè)我們有兩個數(shù)組，長度分別是5, 10，具體數(shù)值如下：
A = [1, 2, 6, 8, 9]
B = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
則，我們要找的中位數(shù)是第(5 + 10 + 1) / 2=8的數(shù)，即k = 8。j假設(shè)我們先合并得到1,1,2,2,3,4,5,6,6,7,8,8,9,9,10，可以看到我們要找的是第8個數(shù)是6.
我們比較兩個數(shù)組的第 k / 2個數(shù)字，也就是比較第4個數(shù)字，A數(shù)組中是6 和B數(shù)組中是4，如果哪個小，就表明該數(shù)組的前 k / 2個數(shù)字都在搜索空間內(nèi)，可以直接排除。這樣B數(shù)據(jù)的前3個值1，2，3, 4都不是第7小的數(shù)字，我們將其排除掉。我們要求的值在
A=[1,2,6,8,9]
B=[5,6,7,8,9,10]
中，將這兩個數(shù)組作為新的數(shù)組進行比較。
由于我們要找的是最小的第k=8個數(shù)字，而此時已經(jīng)排除掉了 3 個數(shù)字，所以在兩個新數(shù)組中，我們要找的是第k = 8 - 3 = 5 個數(shù)字。此時重復(fù)上面的流程，比較第 k / 2 = 2個數(shù)字，A[2] = 2 < B[2] = 6，所以我們可以把A數(shù)組的 [1, 2] 排除掉。我們要求的值在
A=[6,8,9]
B=[5,6,7,8,9,10]
中，繼續(xù)將這兩個數(shù)組作為新的數(shù)組進行比較。
我們要找的是最小的第k=8個數(shù)字，而此時又排除掉了 2 個數(shù)字，所以在兩個新數(shù)組中，我們要找的是第k = 8 - 3 - 2 = 3 個數(shù)字。此時重復(fù)上面的流程，比較第 k / 2 = 1個數(shù)字，A[1] = 6 > B[1] = 5，所以我們可以把B數(shù)組的 [5] 排除掉。我們要求的值在
A=[6,8,9]
B=[6,7,8,9,10]
中，繼續(xù)將這兩個數(shù)組作為新的數(shù)組進行比較。
我們要找的是最小的第k=8個數(shù)字，而此時又排除掉了 1 個數(shù)字，所以在兩個新數(shù)組中，我們要找的是第k = 8 - 3 - 2 - 1 = 2 個數(shù)字。此時重復(fù)上面的流程，比較第 k / 2 = 1個數(shù)字，A[1] = 6 = B[1] = 6，此時我們隨意選擇一個渠道，這里我們可以把B數(shù)組的 [6] 排除掉。我們要求的值在
A=[6,8,9]
B=[7,8,9,10]
我們要找的是最小的第k=8個數(shù)字，而此時又排除掉了 1 個數(shù)字，所以在兩個新數(shù)組中，我們要找的是第k = 8 - 3 - 2 - 1 - 1 = 1 個數(shù)字，此時只需比較數(shù)組A，B的第一個元素那個小就可以了，此時顯然A[1] = 6就是我們要求的值。
代碼如下
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int left = (n + m + 1) / 2;
int right = (n + m + 2) / 2;
//將偶數(shù)和奇數(shù)的情況合并，如果是奇數(shù)，會求兩次同樣的 k 。
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
}
private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
//讓 len1 的長度小于 len2，這樣就能保證如果有數(shù)組空了，一定是 len1
if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
if (len1 == 0) return nums2[start2 + k - 1];
if (k == 1) return Math.min(nums1[start1], nums2[start2]);
int i = start1 + Math.min(len1, k / 2) - 1;
int j = start2 + Math.min(len2, k / 2) - 1;
if (nums1[i] > nums2[j]) {
return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
}
else {
return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}
}
總結(jié)
這道題重點考察對于二分查找的理解和使用，用二分查找的方法將時間復(fù)雜度降為 log 級別。當(dāng)然還有編程細節(jié)需要注意，即奇偶數(shù)的問題，要做到一次bug free還需要多加練習(xí)，注意這些特殊情況和邊界條件。
