原題可以在 LeetCode 上找到，地址：Median of Two Sorted Arrays，難度級別為困難。
不要被困難級別唬到，看完這篇文章，相信你也可以做出來。
乍一看求兩遞增數(shù)組的中位數(shù)并不是很難，因為兩序列有序，所以我們很容想到時間復(fù)雜度為 O(m + n) 的做法：依次取出兩數(shù)組中較小的元素，然后找到中間的元素即可。
但這樣并不是最優(yōu)的，我們還可以實現(xiàn)時間復(fù)雜度為 O(log(m + n)) 的算法，自然而然地我們就能想到二分查找法來求解。
題目是讓找兩數(shù)組的中位數(shù)，我們可以泛化為求兩數(shù)組中第 k 大的元素，那么，求中位數(shù)就是其中的一個特例而已。helper 函數(shù)所起到的作用就是求兩數(shù)組中第 k 大的元素，下面來解釋其原理：
假設(shè)數(shù)組分別記為 A，B，當(dāng)前需要搜索第 k 大的數(shù)，于是我們可以考慮從數(shù)組 A 中取出前 m 個元素，從數(shù)組 B 中取出前 k - m 個元素。由于數(shù)組 A，B 分別排序，則 A[m - 1] 大于從數(shù)組 A 中取出的其他所有元素，B[k - m - 1] 大于數(shù)組 B 中取出的其他所有元素。此時，盡管取出元素之間的相對大小關(guān)系不確定，但 A[m - 1] 與 B[k - m - 1] 的較大者一定是這 k 個元素中最大的。那么，較小的那個元素一定不是第 k 大的，這里留給讀者自己想象。
為敘述方便，假設(shè) A[m - 1] 是較小的那個元素，那么我們可以把 A[0]，A[1]...A[m - 1] 排除掉，并且更新 k 值為 k - m，也就是下一次就是從剩余的元素中尋找第 k - m 大的元素，這樣，我們就完成了一次范圍縮小，同理進(jìn)行下一輪的操作。
那么什么時候停止操作呢？分兩種情況：
當(dāng)某個數(shù)組的數(shù)都被取完了，那么直接返回另一個數(shù)組的后
k個元素即可。當(dāng)
k = 1時，也就是只需再找一個數(shù)即可，也就是取兩者當(dāng)前較小的那個即可。
特別地，我們選取 m = k / 2，下面是我畫的草圖，希望能幫助大家理解。
借助上面的理論，你能寫出相關(guān)代碼了嗎？
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
if (len % 2 == 0) {
return (helper(nums1, 0, nums2, 0, len / 2) + helper(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
}
return helper(nums1, 0, nums2, 0, (len + 1) / 2);
}
private int helper(int[] nums1, int m, int[] nums2, int n, int k) {
if (m >= nums1.length) return nums2[n + k - 1];
if (n >= nums2.length) return nums1[m + k - 1];
if (k == 1) return Math.min(nums1[m], nums2[n]);
int p1 = m + k / 2 - 1;
int p2 = n + k / 2 - 1;
int mid1 = p1 < nums1.length ? nums1[p1] : Integer.MAX_VALUE;
int mid2 = p2 < nums2.length ? nums2[p2] : Integer.MAX_VALUE;
if (mid1 < mid2) {
return helper(nums1, m + k / 2, nums2, n, k - k / 2);
}
return helper(nums1, m, nums2, n + k / 2, k - k / 2);
}
}
我的 GitHub 上本題的題解地址：Median of Two Sorted Arrays，希望可以幫到你。
如果你同我一樣熱愛數(shù)據(jù)結(jié)構(gòu)、算法、LeetCode，可以關(guān)注我 GitHub 上的 LeetCode 題解：awesome-java-leetcode
