描述：
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
翻譯過來就是脖苏，給定兩個(gè)已經(jīng)升序排序過的數(shù)組，求這兩個(gè)數(shù)組的中位數(shù)定踱；中位數(shù)的定義為把兩個(gè)數(shù)組合并過后進(jìn)行升序排序后棍潘，處于數(shù)組中間的那個(gè)數(shù)，此時(shí)如果合并后的數(shù)組元素個(gè)數(shù)為偶數(shù)崖媚，則為中間兩個(gè)數(shù)的平均值蜒谤。
初看起來這就是個(gè)尋找第k小數(shù)的問題，解決方案有很多至扰，最簡(jiǎn)單的就是采用歸并排序的思想把兩個(gè)數(shù)組進(jìn)行合并鳍徽，然后取中間的數(shù)就可以了。但問題在于敢课，這個(gè)題目限定了時(shí)間復(fù)雜度為O(log(m+n))阶祭，而合并算法的時(shí)間復(fù)雜度為O(nlogn)，顯然不合題意直秆。另外一個(gè)方法是設(shè)置一個(gè)雙指針濒募，一開始都指向兩個(gè)數(shù)組的開頭，不停地比較兩個(gè)指針指向的元素的大小圾结，指向小元素的指針的往前移一個(gè)元素去追指向大元素的指針瑰剃，一直移動(dòng)(len1+len2)/2次后就能得到中位數(shù)，但是這個(gè)算法的時(shí)間復(fù)雜度仍然不符合題意筝野，為O(n)
但是注意到這個(gè)題目給定的數(shù)組已經(jīng)是排過序的了晌姚，算法導(dǎo)論中對(duì)order statistic問題進(jìn)行過討論，因此歇竟，在有序又要求log級(jí)的時(shí)間復(fù)雜度挥唠，可以考慮分治策略，采用二分法焕议。
大方向定好了宝磨，但是并不清楚具體要怎么去完成這個(gè)二分法，我們應(yīng)該對(duì)什么去做二分？其實(shí)這個(gè)題目需要找的就是第k小的元素問題唤锉，假設(shè)我們的第k小的數(shù)是在第一個(gè)數(shù)組中找了p次世囊，然后在第二個(gè)數(shù)組中找了q次，那么滿足關(guān)系：p+q=k窿祥。進(jìn)一步的茸习，尋找第k小的數(shù)的過程就是尋找p和q的過程，k我們是知道的壁肋，但是p和q是不知道的号胚，因此事實(shí)上我們的目標(biāo)就是去搜索p（找到了p就等于找到了q），因此我們二分法的目標(biāo)浸遗，事實(shí)上就是二分k來找p猫胁。
我們先定義以下形式的函數(shù)用來尋找第k小的數(shù)：
findKth(nums1, nums2, start1, len1, start2, len2, k)
nums1和nums2表示原始的兩個(gè)數(shù)組，start1跛锌、len1表示nums1數(shù)組中以start1位置開始弃秆、len1長(zhǎng)度的一個(gè)子數(shù)組；start2髓帽、lens2表示nums2數(shù)組中以start2位置開始菠赚、len2長(zhǎng)度的一個(gè)子數(shù)組；k表示從這兩個(gè)子數(shù)組中找到第k小的數(shù)郑藏。之所以提供start1衡查、len1、start2必盖、len2拌牲，是因?yàn)榻?jīng)驗(yàn)告訴我們分治法解決問題都是遞歸的，我們?cè)诙值臅r(shí)候就需要記錄這些相關(guān)的數(shù)據(jù)歌粥。
我們的外層入口就應(yīng)該是這樣子的：
if(len1+len2是偶數(shù)) {
return (findKth(nums1, nums2, 0, len1, 0, len2, (len1+len2)/2) +
findKth(nums1, nums2, 0, len1, 0, len2, (len1+len2)/2 + 1)) / 2;
}
else {
return findKth(nums1, nums2, 0, len1, 0, len2 (len1+len2)/2);
}
下面就是具體對(duì)于findKth的實(shí)現(xiàn)了塌忽。
首先，我們知道失驶，我們需要對(duì)k進(jìn)行二分：
findKth(nums1, nums2, start1, len1, start2, len2, k) {
p = k / 2;
}
這個(gè)p怎么用呢土居？假設(shè)我們?cè)趎ums1中取nums1[start1+p-1]，就表示我們?cè)趎ums1中“前進(jìn)”了p個(gè)元素嬉探，且這p個(gè)元素是有序的擦耀，相應(yīng)的，q = k - p甲馋，我們需要在nums2中前進(jìn)q個(gè)元素：
findKth(nums1, nums2, start1, len1, start2, len2, k) {
p = k / 2;
q = k - p;
}
假如這個(gè)時(shí)候nums1[start1 + p - 1]等于nums2[start + q - 1]埂奈，這說明kth = nums1[start1 + p - 1] = nums2[start + q - 1] = 第k小的數(shù)迄损，為什么呢定躏？這里要注意nums1和nums2都是有序的，因此它們的子數(shù)組也是有序的；假設(shè)把兩個(gè)子數(shù)組數(shù)組合并痊远，那么在nums1子數(shù)組中排在kth前面的數(shù)在合并后的數(shù)組中一定還是排在kth前面垮抗，同理在nums2子數(shù)組中排在kth前面的數(shù)在合并后的數(shù)組中也一定還是排在kth前面，它們的具體順序我們不關(guān)心也不必關(guān)心碧聪，我們只需要知道這樣一來在合并后的數(shù)組中就有p-1+q-1=k-2個(gè)數(shù)在kth前面冒版，因此kth一定就是第k小的那個(gè)數(shù)。
如果nums1[start1 + p - 1]大于nums2[start + q - 1]逞姿，這里就出現(xiàn)了一個(gè)需要注意的情況辞嗡，這意味著nums2子數(shù)組中的前q個(gè)數(shù)一定都是小于nums1[start1 + p - 1]的（再次注意，nums1和nums2都是有序的）滞造，而q<k续室，這也就意味著第k小的數(shù)一定不會(huì)出現(xiàn)在nums2的子數(shù)組的前q個(gè)數(shù)中。這啟發(fā)我們?cè)谶@個(gè)時(shí)候就可以拋棄掉前q個(gè)數(shù)谒养，重新用一個(gè)新的子數(shù)組進(jìn)行搜索挺狰，注意，進(jìn)一步的搜索中由于拋棄掉了q（p）個(gè)數(shù)买窟，因此下一步在子數(shù)組中的搜索中丰泊，事實(shí)上就是在搜索第k-q（k-p）小的元素了：
findKth(nums1, nums2, start1, len1, start2, len2, k) {
p = k / 2;
q = k - p;
if(nums1[start1 + p - 1] == nums2[start2 + q - 1]) {
return nums1[start1 + p - 1];
}
else if(nums1[start1 + p - 1] > nums2[start2 + q - 1]) {
return findKth(nums1, nums2, start1, len1, start2 + q, len2 - q, k - q);
}
else if(nums1[start1 + p - 1] < nums2[start2 + q - 1]) {
return findKth(nums1, nums2, start1 + p, len1 - p, start2, len2, k - p);
}
}
上面的框架大致已經(jīng)描述清楚了我們的二分搜索算法，下一步就需要考慮退出條件始绍。
退出條件有這么一些：
- 在某一步搜索中子數(shù)組的長(zhǎng)度為0了瞳购，這表示有一個(gè)數(shù)組中的元素完全被拋棄掉，此時(shí)另外一個(gè)子數(shù)組的第k個(gè)元素就是我們要求的第k小的元素亏推；
- 在不滿足1的情況下苛败，出現(xiàn)k=1的情況，這表示需要在兩個(gè)子數(shù)組中找第1小的元素径簿，此時(shí)簡(jiǎn)單地比較一下兩個(gè)子數(shù)組的第一個(gè)元素就行了罢屈；
- nums1[start1 + p - 1] == nums2[start2 + q - 1]
因此可以進(jìn)一步寫成：
findKth(nums1, nums2, start1, len1, start2, len2, k) {
if(某個(gè)子數(shù)組的長(zhǎng)度為零) {
return 另外一個(gè)子數(shù)組的第k個(gè)元素;
}
if(k == 1) {
return min(nums1[start1], nums2[start2]);
}
p = k / 2;
q = k - p;
if(nums1[start1 + p - 1] == nums2[start2 + q - 1]) {
return nums1[start1 + p - 1];
}
else if(nums1[start1 + p - 1] > nums2[start2 + q - 1]) {
return findKth(nums1, nums2, start1, len1, start2 + q, len2 - q, k - q);
}
else if(nums1[start1 + p - 1] < nums2[start2 + q - 1]) {
return findKth(nums1, nums2, start1 + p, len1 - p, start2, len2, k - p);
}
}
為了方便考慮問題，不失一般性篇亭，我們要求nums1永遠(yuǎn)是那個(gè)長(zhǎng)度較短的數(shù)組：
findKth(nums1, nums2, start1, len1, start2, len2, k) {
if(len1 > len2) {
return findKth(nums2, nums1, start2, len2, start2, start1);
}
if(len1 == 0) {
return nums2[start2 + k - 1];
}
if(k == 1) {
return min(nums1[start1], nums2[start2]);
}
p = k / 2;
q = k - p;
if(nums1[start1 + p - 1] == nums2[start2 + q - 1]) {
return nums1[start1 + p - 1];
}
else if(nums1[start1 + p - 1] > nums2[start2 + q - 1]) {
return findKth(nums1, nums2, start1, len1, start2 + q, len2 - q, k - q);
}
else if(nums1[start1 + p - 1] < nums2[start2 + q - 1]) {
return findKth(nums1, nums2, start1 + p, len1 - p, start2, len2, k - p);
}
}
此外還有一個(gè)容易被忽略的邊界問題缠捌，那就是p=k/2這一句，如果p大于len1的話译蒂，就會(huì)出現(xiàn)越界訪問的問題曼月，這個(gè)時(shí)候需要對(duì)其進(jìn)行控制：
findKth(nums1, nums2, start1, len1, start2, len2, k) {
if(len1 > len2) {
return findKth(nums2, nums1, start2, len2, start2, start1);
}
if(len1 == 0) {
return nums2[start2 + k - 1];
}
if(k == 1) {
return min(nums1[start1], nums2[start2]);
}
p = min(k / 2, len1);
q = k - p;
if(nums1[start1 + p - 1] == nums2[start2 + q - 1]) {
return nums1[start1 + p - 1];
}
else if(nums1[start1 + p - 1] > nums2[start2 + q - 1]) {
return findKth(nums1, start1, len1, start2 + q, len2 - q, k - q);
}
else if(nums1[start1 + p - 1] > nums2[start2 + q - 1]) {
return findKth(nums1, start1 + p, len1 - p, start2, len2, k - p);
}
}
分析到這里，基本上這個(gè)問題就解決了柔昼，不過需要說的是哑芹，對(duì)于p=min(k/2,len1)這一句，這里看起來應(yīng)該就是二分法的比較關(guān)鍵的一個(gè)地方了捕透，事實(shí)上我們把2換成3聪姿、4碴萧、5、6……都是可以的末购，因?yàn)槎址ㄋ阉魇聦?shí)上就是個(gè)碰運(yùn)氣的過程破喻，不過需要注意的是，這里p不能為0盟榴，否則在nums1中等于是沒有做“前進(jìn)”的動(dòng)作曹质，這是不允許的，因此更加健壯的描述應(yīng)該為：
p = min(max(k/2, 1), len1);
即二分過程中擎场，每一次迭代至少要在nums1中“前進(jìn)”一步羽德。
整個(gè)程序的C++代碼如下：
#include <vector>
class Solution {
private:
double findKth(vector<int>& nums1, vector<int>& nums2, int start1, int len1, int start2, int len2, int k) {
if (len1 > len2) {
return findKth(nums2, nums1, start2, len2, start1, len1, k);
}
if (len1 == 0) {
return nums2[start2 + k - 1];
}
if (k == 1) {
return min(nums1[start1], nums2[start2]);
}
int p1 = min(k / 2, len1);
int p2 = k - p1;
if (nums1[start1 + p1 - 1] > nums2[start2 + p2 - 1]) {
return findKth(nums1, nums2, start1, len1, start2 + p2, len2 - p2, k - p2);
}
else if(nums1[start1 + p1 - 1] < nums2[start2 + p2 - 1]){
return findKth(nums1, nums2, start1 + p1, len1 - p1, start2, len2, k - p1);
}
else {
return nums1[start1 + p1 - 1];
}
}
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len = nums1.size() + nums2.size();
if (!(len & 0x01)) {
return (findKth(nums1, nums2, 0, nums1.size(), 0, nums2.size(), len / 2)
+ findKth(nums1, nums2, 0, nums1.size(), 0, nums2.size(), len / 2 + 1)
) / 2.0f;
}
else {
return findKth(nums1, nums2, 0, nums1.size(), 0, nums2.size(), len / 2 + 1);
}
}
};
