https://leetcode.windliang.cc/ 第一時(shí)間發(fā)布
題目描述（困難難度）
已知兩個(gè)有序數(shù)組鸿染，找到兩個(gè)數(shù)組合并后的中位數(shù)指蚜。
解法一
簡(jiǎn)單粗暴，先將兩個(gè)數(shù)組合并涨椒，兩個(gè)有序數(shù)組的合并也是歸并排序中的一部分摊鸡。然后根據(jù)奇數(shù)，還是偶數(shù)蚕冬，返回中位數(shù)免猾。
代碼
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];
}
}
時(shí)間復(fù)雜度：遍歷全部數(shù)組，O（m + n）
空間復(fù)雜度：開辟了一個(gè)數(shù)組囤热，保存合并后的兩個(gè)數(shù)組猎提，O（m + n）
解法二
其實(shí)，我們不需要將兩個(gè)數(shù)組真的合并旁蔼，我們只需要找到中位數(shù)在哪里就可以了锨苏。
開始的思路是寫一個(gè)循環(huán)疙教，然后里邊判斷是否到了中位數(shù)的位置，到了就返回結(jié)果伞租，但這里對(duì)偶數(shù)和奇數(shù)的分類會(huì)很麻煩松逊。當(dāng)其中一個(gè)數(shù)組遍歷完后，出了 for 循環(huán)對(duì)邊界的判斷也會(huì)分幾種情況肯夏【辏總體來(lái)說(shuō)，雖然復(fù)雜度不影響驯击，但代碼會(huì)看起來(lái)很亂烁兰。然后在 這里 找到了另一種思路。
首先是怎么將奇數(shù)和偶數(shù)的情況合并一下徊都。
用 len 表示合并后數(shù)組的長(zhǎng)度沪斟，如果是奇數(shù)，我們需要知道第 （len + 1）/ 2 個(gè)數(shù)就可以了暇矫，如果遍歷的話需要遍歷 int ( len / 2 ) + 1 次主之。如果是偶數(shù)，我們需要知道第 len / 2 和 len / 2 + 1 個(gè)數(shù)李根，也是需要遍歷 len / 2 + 1 次槽奕。所以遍歷的話，奇數(shù)和偶數(shù)都是 len / 2 + 1 次房轿。
返回中位數(shù)的話粤攒，奇數(shù)需要最后一次遍歷的結(jié)果就可以了，偶數(shù)需要最后一次和上一次遍歷的結(jié)果囱持。所以我們用兩個(gè)變量 left 和 right 夯接，right 保存當(dāng)前循環(huán)的結(jié)果，在每次循環(huán)前將 right 的值賦給 left 纷妆。這樣在最后一次循環(huán)的時(shí)候盔几，left 將得到 right 的值，也就是上一次循環(huán)的結(jié)果掩幢，接下來(lái) right 更新為最后一次的結(jié)果逊拍。
循環(huán)中該怎么寫，什么時(shí)候 A 數(shù)組后移粒蜈，什么時(shí)候 B 數(shù)組后移顺献。用 aStart 和 bStart 分別表示當(dāng)前指向 A 數(shù)組和 B 數(shù)組的位置。如果 aStart 還沒(méi)有到最后并且此時(shí) A 位置的數(shù)字小于 B 位置的數(shù)組枯怖，那么就可以后移了注整。也就是aStart ＜ m && A[aStart] < B[bStart]。
但如果 B 數(shù)組此刻已經(jīng)沒(méi)有數(shù)字了，繼續(xù)取數(shù)字B [ bStart ]肿轨，則會(huì)越界寿冕，所以判斷下 bStart 是否大于數(shù)組長(zhǎng)度了，這樣 || 后邊的就不會(huì)執(zhí)行了椒袍，也就不會(huì)導(dǎo)致錯(cuò)誤了驼唱，所以增加為 aStart ＜ m && ( bStart >= n || A [ aStart ] < B [ bStart ] ) 髓介。
代碼
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;
}
時(shí)間復(fù)雜度：遍歷 len/2 + 1 次隔缀，len = m + n 隧土，所以時(shí)間復(fù)雜度依舊是 O（m + n）芋齿。
空間復(fù)雜度：我們申請(qǐng)了常數(shù)個(gè)變量，也就是 m饥努，n矛缨，len而昨，left帆焕，right惭婿，aStart，bStart 以及 i 叶雹。
總共 8 個(gè)變量财饥，所以空間復(fù)雜度是 O（1）。
解法三
上邊的兩種思路折晦，時(shí)間復(fù)雜度都達(dá)不到題目的要求 O ( log ( m + n ) )钥星。看到 log 筋遭，很明顯打颤，我們只有用到二分的方法才能達(dá)到。我們不妨用另一種思路漓滔，題目是求中位數(shù)，其實(shí)就是求第 k 小數(shù)的一種特殊情況乖篷，而求第 k 小數(shù)有一種算法响驴。
解法二中，我們一次遍歷就相當(dāng)于去掉不可能是中位數(shù)的一個(gè)值撕蔼，也就是一個(gè)一個(gè)排除豁鲤。由于數(shù)列是有序的，其實(shí)我們完全可以一半兒一半兒的排除鲸沮。假設(shè)我們要找第 k 小數(shù)琳骡，我們可以每次循環(huán)排除掉 k / 2 個(gè)數(shù)∷夏纾看下邊一個(gè)例子楣号。
假設(shè)我們要找第 7 小的數(shù)字。
我們比較兩個(gè)數(shù)組的第 k / 2 個(gè)數(shù)字，如果 k 是奇數(shù)炫狱，向下取整藻懒。也就是比較第 3 個(gè)數(shù)字，上邊數(shù)組中的 8 和 下邊數(shù)組中的 3 视译，如果哪個(gè)小嬉荆，就表明該數(shù)組的前 k / 2 個(gè)數(shù)字都不是第 k 小數(shù)字，所以可以排除酷含。也就是 1鄙早，2，3 這三個(gè)數(shù)字不可能是第 7 小的數(shù)字椅亚，我們可以把它排除掉蝶锋。將 1389 和 45678910 兩個(gè)數(shù)組作為新的數(shù)組進(jìn)行比較。
更一般的情況 A [ 1 ]什往，A [ 2 ]扳缕，A [ 3 ]，A [ k / 2] ... 别威，B[ 1 ]躯舔，B [ 2 ]，B [ 3 ]省古，B[ k / 2] ... 粥庄，如果 A [ k / 2 ] < B [ k / 2 ] ，那么 A [ 1 ]豺妓，A [ 2 ]惜互，A [ 3 ]，A [ k / 2] 都不可能是第 k 小的數(shù)字琳拭。
A 數(shù)組中比 A [ k / 2 ] 小的數(shù)有 k / 2 - 1 個(gè)训堆，B 數(shù)組中，B [ k / 2 ] 比 A [ k / 2 ] 小白嘁，假設(shè) B [ k / 2 ] 前邊的數(shù)字都比 A [ k / 2 ] 小坑鱼，也只有 k / 2 - 1 個(gè)，所以比 A [ k / 2 ] 小的數(shù)字最多有 k / 2 - 1 + k / 2 - 1 = k - 2 個(gè)絮缅，所以 A [ k / 2 ] 最多是第 k - 1 小的數(shù)鲁沥。而比 A [ k / 2 ] 小的數(shù)更不可能是第 k 小的數(shù)了，所以可以把它們排除耕魄。
橙色的部分表示已經(jīng)去掉的數(shù)字画恰。
由于我們已經(jīng)排除掉了 3 個(gè)數(shù)字，就是這 3 個(gè)數(shù)字一定在最前邊吸奴，所以在兩個(gè)新數(shù)組中允扇，我們只需要找第 7 - 3 = 4 小的數(shù)字就可以了缠局，也就是 k = 4 。此時(shí)兩個(gè)數(shù)組蔼两，比較第 2 個(gè)數(shù)字甩鳄，3 < 5，所以我們可以把小的那個(gè)數(shù)組中的 1 额划，3 排除掉了妙啃。
我們又排除掉 2 個(gè)數(shù)字，所以現(xiàn)在找第 4 - 2 = 2 小的數(shù)字就可以了俊戳。此時(shí)比較兩個(gè)數(shù)組中的第 k / 2 = 1 個(gè)數(shù)揖赴，4 = 4 ，怎么辦呢抑胎？由于兩個(gè)數(shù)相等燥滑，所以我們無(wú)論去掉哪個(gè)數(shù)組中的都行，因?yàn)槿サ?1 個(gè)總會(huì)保留 1 個(gè)的阿逃，所以沒(méi)有影響铭拧。為了統(tǒng)一，我們就假設(shè) 4 > 4 吧恃锉，所以此時(shí)將下邊的 4 去掉搀菩。
由于又去掉 1 個(gè)數(shù)字，此時(shí)我們要找第 1 小的數(shù)字破托，所以只需判斷兩個(gè)數(shù)組中第一個(gè)數(shù)字哪個(gè)小就可以了肪跋，也就是 4 。
所以第 7 小的數(shù)字是 4 土砂。
我們每次都是取 k / 2 的數(shù)進(jìn)行比較州既，有時(shí)候可能會(huì)遇到數(shù)組長(zhǎng)度小于 k / 2 的時(shí)候。
此時(shí) k / 2 等于 3 萝映，而上邊的數(shù)組長(zhǎng)度是 2 吴叶，我們此時(shí)將箭頭指向它的末尾就可以了。這樣的話锌俱，由于 2 < 3 晤郑，所以就會(huì)導(dǎo)致上邊的數(shù)組 1，2 都被排除贸宏。造成下邊的情況。
由于 2 個(gè)元素被排除磕洪，所以此時(shí) k = 5 吭练，又由于上邊的數(shù)組已經(jīng)空了，我們只需要返回下邊的數(shù)組的第 5 個(gè)數(shù)字就可以了析显。
從上邊可以看到鲫咽，無(wú)論是找第奇數(shù)個(gè)還是第偶數(shù)個(gè)數(shù)字，對(duì)我們的算法并沒(méi)有影響，而且在算法進(jìn)行中分尸，k 的值都有可能從奇數(shù)變?yōu)榕紨?shù)锦聊，最終都會(huì)變?yōu)?1 或者由于一個(gè)數(shù)組空了，直接返回結(jié)果箩绍。
所以我們采用遞歸的思路孔庭，為了防止數(shù)組長(zhǎng)度小于 k / 2 ，所以每次比較 min ( k / 2材蛛，len ( 數(shù)組 ) ) 對(duì)應(yīng)的數(shù)字圆到，把小的那個(gè)對(duì)應(yīng)的數(shù)組的數(shù)字排除，將兩個(gè)新數(shù)組進(jìn)入遞歸卑吭，并且 k 要減去排除的數(shù)字的個(gè)數(shù)芽淡。遞歸出口就是當(dāng) k = 1 或者其中一個(gè)數(shù)字長(zhǎng)度是 0 了。
代碼
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ù)挣菲，會(huì)求兩次同樣的 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 的長(zhǎng)度小于 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));
}
}
時(shí)間復(fù)雜度：每進(jìn)行一次循環(huán)，我們就減少 k / 2 個(gè)元素耙饰，所以時(shí)間復(fù)雜度是 O（log（k））纹笼，而 k = （m + n）/ 2 ，所以最終的復(fù)雜也就是 O（log（m + n））苟跪。
空間復(fù)雜度：雖然我們用到了遞歸廷痘，但是可以看到這個(gè)遞歸屬于尾遞歸，所以編譯器不需要不停地堆棧件已，所以空間復(fù)雜度為 O（1）笋额。
解法四
我們首先理一下中位數(shù)的定義是什么
中位數(shù)（又稱中值，英語(yǔ)：Median）篷扩，統(tǒng)計(jì)學(xué)中的專有名詞兄猩，代表一個(gè)樣本、種群或概率分布中的一個(gè)數(shù)值鉴未，其可將數(shù)值集合劃分為相等的上下兩部分枢冤。
所以我們只需要將數(shù)組進(jìn)行切。
一個(gè)長(zhǎng)度為 m 的數(shù)組铜秆，有 0 到 m 總共 m + 1 個(gè)位置可以切淹真。
我們把數(shù)組 A 和數(shù)組 B 分別在 i 和 j 進(jìn)行切割。
將 i 的左邊和 j 的左邊組合成「左半部分」连茧，將 i 的右邊和 j 的右邊組合成「右半部分」核蘸。
-
當(dāng) A 數(shù)組和 B 數(shù)組的總長(zhǎng)度是偶數(shù)時(shí)巍糯，如果我們能夠保證
-
左半部分的長(zhǎng)度等于右半部分
i + j = m - i + n - j , 也就是 j = ( m + n ) / 2 - i
-
左半部分最大的值小于等于右半部分最小的值 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））
那么，中位數(shù)就可以表示如下
（左半部分最大值 + 右半部分最大值 ）/ 2 客扎。
（max ( A [ i - 1 ] , B [ j - 1 ]）+ min ( A [ i ] , B [ j ]）） / 2
-
-
當(dāng) A 數(shù)組和 B 數(shù)組的總長(zhǎng)度是奇數(shù)時(shí)祟峦，如果我們能夠保證
-
左半部分的長(zhǎng)度比右半部分大 1
i + j = m - i + n - j + 1也就是 j = ( m + n + 1) / 2 - i
左半部分最大的值小于等于右半部分最小的值 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））
那么，中位數(shù)就是 左半部分最大值徙鱼，也就是左半部比右半部分多出的那一個(gè)數(shù)宅楞。 max ( A [ i - 1 ] , B [ j - 1 ]） -
上邊的第一個(gè)條件我們其實(shí)可以合并為 j = ( m + n + 1) / 2 - i，因?yàn)槿绻?m + n 是偶數(shù)疆偿，由于我們?nèi)〉氖?int 值咱筛，所以加 1 也不會(huì)影響結(jié)果。當(dāng)然杆故，由于 0 <= i <= m 迅箩，為了保證 0 <= j <= n ，我們必須保證 m <= n 处铛。
最后一步由于是 int 間的運(yùn)算饲趋，所以 1 / 2 = 0。
而對(duì)于第二個(gè)條件撤蟆，奇數(shù)和偶數(shù)的情況是一樣的奕塑，我們進(jìn)一步分析。為了保證 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））家肯，因?yàn)?A 數(shù)組和 B 數(shù)組是有序的龄砰，所以 A [ i - 1 ] <= A [ i ]，B [ i - 1 ] <= B [ i ] 這是天然的讨衣，所以我們只需要保證 B [ j - 1 ] < = A [ i ] 和 A [ i - 1 ] <= B [ j ] 所以我們分兩種情況討論：
-
B [ j - 1 ] > A [ i ]换棚，并且為了不越界，要保證 j != 0反镇，i != m
image此時(shí)很明顯固蚤，我們需要增加 i ，為了數(shù)量的平衡還要減少 j 歹茶，幸運(yùn)的是 j = ( m + n + 1) / 2 - i夕玩，i 增大，j 自然會(huì)減少惊豺。
-
A [ i - 1 ] > B [ j ] 燎孟，并且為了不越界，要保證 i != 0尸昧，j != n
image此時(shí)和上邊的情況相反缤弦，我們要減少 i ，增大 j 彻磁。
上邊兩種情況碍沐，我們把邊界都排除了，需要單獨(dú)討論衷蜓。
-
當(dāng) i = 0 , 或者 j = 0 累提，也就是切在了最前邊。
image此時(shí)左半部分當(dāng) j = 0 時(shí)磁浇，最大的值就是 A [ i - 1 ] 斋陪；當(dāng) i = 0 時(shí) 最大的值就是 B [ j - 1] 。右半部分最小值和之前一樣置吓。
-
當(dāng) i = m 或者 j = n 无虚，也就是切在了最后邊。
image此時(shí)左半部分最大值和之前一樣衍锚。右半部分當(dāng) j = n 時(shí)友题，最小值就是 A [ i ] ；當(dāng) i = m 時(shí)戴质，最小值就是B [ j ] 度宦。
所有的思路都理清了，最后一個(gè)問(wèn)題告匠，增加 i 的方式戈抄。當(dāng)然用二分了。初始化 i 為中間的值后专，然后減半找中間的划鸽，減半找中間的，減半找中間的直到答案戚哎。
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) {
return findMedianSortedArrays(B,A); // 保證 m <= n
}
int iMin = 0, iMax = m;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = (m + n + 1) / 2 - i;
if (j != 0 && i != m && B[j-1] > A[i]){ // i 需要增大
iMin = i + 1;
}
else if (i != 0 && j != n && A[i-1] > B[j]) { // i 需要減小
iMax = i - 1;
}
else { // 達(dá)到要求裸诽，并且將邊界條件列出來(lái)單獨(dú)考慮
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i-1]; }
else { maxLeft = Math.max(A[i-1], B[j-1]); }
if ( (m + n) % 2 == 1 ) { return maxLeft; } // 奇數(shù)的話不需要考慮右半部分
int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }
return (maxLeft + minRight) / 2.0; //如果是偶數(shù)的話返回結(jié)果
}
}
return 0.0;
}
}
時(shí)間復(fù)雜度：我們對(duì)較短的數(shù)組進(jìn)行了二分查找，所以時(shí)間復(fù)雜度是 O（log（min（m建瘫，n）））崭捍。
空間復(fù)雜度：只有一些固定的變量，和數(shù)組長(zhǎng)度無(wú)關(guān)啰脚，所以空間復(fù)雜度是 O ( 1 ) 殷蛇。
總結(jié)
解法二中體會(huì)到了對(duì)情況的轉(zhuǎn)換，有時(shí)候即使有了思路橄浓，代碼也不一定寫的優(yōu)雅粒梦，需要多鍛煉才可以。解法三和解法四充分發(fā)揮了二分查找的優(yōu)勢(shì)荸实，將時(shí)間復(fù)雜度降為 log 級(jí)別匀们。
