尋找兩個有序數(shù)組的中位數(shù)
非常好的講解
題目
給定兩個大小為 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
解題思路分析
這道題的直觀解法：就是掃一遍兩個數(shù)組，找到中間位置的那一個/兩個數(shù)性锭，然后得到中位數(shù)。時間復(fù)雜度是 O(m+n)叫胖，其中 m 和 n 分別是數(shù)組 A 和數(shù)組 B 的長度草冈。
但是！面試官會這么輕易就放過你嗎？顯然是不可能滴~~我偷看了一下題目描述下的“challenge”標(biāo)簽怎棱，原來這道題的最優(yōu)解是 O(log(m + n)) 的復(fù)雜度哩俭。(m + n) 是倆數(shù)組合并后的總長度 L，看到 O(log L) 這樣的復(fù)雜度拳恋，而且還是有序數(shù)組凡资，能想到哪個算法嗎？沒錯谬运，就是二分查找隙赁！那我們試試。梆暖。
如果我取出 A[i] 伞访，用二分查找在數(shù)組 B 中找到 A[i] 可以插入的位置，假設(shè) A[i] 在 B 中的插入位置是 j式廷，那么 A[i] 在整個合并數(shù)組中的位置就是 (i + j) ，因為要求的中位數(shù)的位置是 (m + n) / 2芭挽，通過比較 (i + j) 和 (m + n) / 2 的大小可以每次舍棄 A 的一部分滑废，從而收斂數(shù)組 A。用同樣的方法可以收斂數(shù)組 B袜爪。但是這樣的復(fù)雜度是 O(log m * log n)蠕趁，復(fù)雜度大于 O(log(m + n))，顯然不是最優(yōu)的辛馆。
那如果不是直接使用二分查找算法俺陋，而是借用二分查找的思想呢？就是每次有選擇地舍棄掉數(shù)組的一部分昙篙，從而達(dá)到收斂數(shù)組縮小查找范圍的效果腊状。
a. 我們重新看題目，要找中位數(shù)苔可，就是要找第 k 大的數(shù)（k = (L / 2 + 1)缴挖，其中L 是上面提到的合并后新數(shù)組的長度，當(dāng) L 是偶數(shù)時焚辅，要求第 (L / 2) 大和第 (L / 2 + 1) 大的兩個數(shù)）映屋。當(dāng)我們舍棄掉一部分，假設(shè)舍棄部分的長度為 length同蜻，那么接下來就是在剩下的數(shù)組里求第 (k - length) 大的數(shù)棚点。逐層縮小范圍，直到兩數(shù)組其中一個走完湾蔓，或者要求的是第 1 大的元素瘫析，就可以直接返回結(jié)果了。
b. 那如何“選擇”要舍棄哪部分呢？既然是要找合并后的數(shù)組 C 的第 k 大元素颁股，即 C[k-1]么库，那如果我們從 A 和 B 中分別取前 k/2 個元素，其中必然有一部分是是在數(shù)組 C 的前 k 個數(shù)里甘有。設(shè) mid = k / 2诉儒，當(dāng) A[mid - 1] < B[mid - 1] 時，可以斷定 A 的前 mid 個元素是在 C 的前 k 個數(shù)里（此處可用反證法得證）亏掀，那么我們則舍棄 A 的前 mid 個元素忱反。反之則舍棄 B 的前 mid 個元素。現(xiàn)在數(shù)組 A 或者 B 已經(jīng)舍棄掉 k/2 個元素滤愕，縮小查找范圍了温算，那接下來可以按照同樣的方法繼續(xù)選擇嗎？當(dāng)然间影！現(xiàn)在剩下總共 (L - mid) 個元素注竿，且 A 和 B 依舊有序，要找的是第 (k - mid) 大的元素魂贬，所以我們可以按照上面的方法繼續(xù)遞歸選擇下去巩割，直到找到目標(biāo)元素！
c. 復(fù)雜度分析：每次從合并后數(shù)組 C 里減少 k/2 個元素付燥，直到找到目標(biāo)元素宣谈。所以時間復(fù)雜度是 O(log L) = O(log (m + n)) ！
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
/**
如果兩個數(shù)組的中位數(shù) mid1 < mid2, 則說明合并后的中位數(shù)位于 num1.right + num2之間
否則合并后的中位數(shù)位于 nums2.right + nums1 之間 (right 是相對于 mid 而言的)
getKth 函數(shù)負(fù)責(zé)找到兩個數(shù)組合并(假設(shè))后有序的數(shù)組中的第 k 個元素, k 從 1 開始計算
**/
if(nums1.length == 0 && nums2.length == 0) return 0.0;
int m = nums1.length, n = nums2.length;
// l: 合并后數(shù)組的左半部分的最后一個數(shù) r: 合并后數(shù)組的右半部分的第一個數(shù)
int l = (m+n+1) / 2;
int r = (m+n+2) / 2;
// 如果 m+n 是奇數(shù) getKth 的返回值是相同的, 是偶數(shù)則是合并后數(shù)組的中間兩個數(shù)
if(l == r) return getKth(nums1, 0, nums2, 0, l);
return (getKth(nums1, 0, nums2, 0, l) + getKth(nums1, 0, nums2, 0, r)) / 2.0;
}
private double getKth(int[] nums1, int st1, int[] nums2, int st2, int k) {
// 邊界情況, 如果 nums1數(shù)組已經(jīng)窮盡了, 則只能返回 nums2 中的第 k 個元素
if(st1 > nums1.length-1) return nums2[st2 + k - 1];
if(st2 > nums2.length-1) return nums1[st1 + k - 1];
// 邊界情況, k = 1 則返回兩個數(shù)組中最小的那個
if(k == 1) return Math.min(nums1[st1], nums2[st2]);
// 在 nums1 和 nums2 當(dāng)前范圍內(nèi)找出 mid1 和 mid2 判斷舍棄哪半部分
int mid1 = Integer.MAX_VALUE;
int mid2 = Integer.MAX_VALUE;
if(st1 + k/2 - 1 < nums1.length) mid1 = nums1[st1 + k/2 - 1];
if(st2 + k/2 - 1 < nums2.length) mid2 = nums2[st2 + k/2 - 1];
// mid1 < mid2 在 nums1.right 和 nums2 之間搜索, 丟掉 k/2 個數(shù).
if(mid1 < mid2)
return getKth(nums1, st1 + k/2, nums2, st2, k - k/2);
else
return getKth(nums1, st1, nums2, st2 + k/2, k - k/2);
}
}
