求兩個有序數(shù)組的中位數(shù)或者第k小元素
（給算法愛好者加星標，修煉編程內(nèi)功）
作者：JustDoIT
https://www.cnblogs.com/TenosDoIt/p/3554479.html
問題：兩個已經(jīng)排好序的數(shù)組，找出兩個數(shù)組合并后的中位數(shù)（如果兩個數(shù)組的元素數(shù)目是偶數(shù)，返回上中位數(shù)）。
設兩個數(shù)組分別是vec1和vec2，元素數(shù)目分別是n1、n2。
?
算法1：最簡單的辦法就是把兩個數(shù)組合并、排序，然后返回中位數(shù)即可，由于兩個數(shù)組原本是有序的，因此可以用歸并排序中的merge步驟合并兩個數(shù)組。
由于我們只需要返回中位數(shù)，因此并不需要真的合并兩個數(shù)組，只需要模擬合并兩個數(shù)組：每次選數(shù)組中較小的數(shù)，統(tǒng)計到第（n1+n2+1）/2個元素就是要找的中位數(shù)。算法復雜度為O(n1+n2)
int findMedian_merge(vector<int> &vec1, vector<int> &vec2){int N1 = vec1.size(), N2 = vec2.size();int medean = (N1 + N2 + 1) / 2, i = 0, j = 0;for(int k = 1; k < medean; k++){if(i < N1 && j < N2){if(vec1[i] < vec2[j])i++;else j++;}else if(i >= N1)//數(shù)組vec1到達末尾j++;else if(j >= N2)//數(shù)組vec2到達末尾i++;}if(i < N1 && j < N2)return vec1[i] < vec2[j] ? vec1[i] : vec2[j];else if(i >= N1)return vec2[j];else if(j >= N2)return vec1[i];}
講下面的算法之前，先說2個結(jié)論
結(jié)論1：某個數(shù)組中有一半的元素不超過數(shù)組的中位數(shù)，有一半的元素不小于中位數(shù)（如果數(shù)組中元素個數(shù)是偶數(shù)，那么這里的一半并不是嚴格意義的1/2）。
結(jié)論2：如果我們?nèi)サ魯?shù)組比中位數(shù)小的k個數(shù)，再去掉比中位數(shù)大的k個數(shù)，得到的子數(shù)組的中位數(shù)和原來的中位數(shù)相同。
算法2：利用折半查找的思想，假設兩個數(shù)組的中位數(shù)分別是vec1[m1], vec2[m2]?
1、如果vec1[m1] = vec2[m2] ，那么剛好有一半元素不超過vec1[m1]，則vec1[m1]就是要找的中位數(shù)。
2、如果vec1[m1] < vec2[m2] 根據(jù)結(jié)論1很容易可以推理出，這個中位數(shù)只可能出現(xiàn)在vec1[n1/2,…,n1-1]或vec2[0,…,(n2-1)/2]中，那么vec1[n1/2,…,n1-1]和vec2[0,…,(n2-1)/2]的中位數(shù)是不是和原來兩個數(shù)組的中位數(shù)相同呢？
根據(jù)結(jié)論2，如果原數(shù)組長度相等，即n1=n2，那么中位數(shù)不變；如果長度不相等，vec2中去掉的大于中位數(shù)的數(shù)的個數(shù) > vec1中去掉的小于中位數(shù)的數(shù)的個數(shù) ，則中位數(shù)不一定不變。因此我們要在兩個數(shù)組中去掉相同個數(shù)的元素。
如下圖所示，假設n1 < n2, 兩個數(shù)組都去掉n1/2個元素，則子數(shù)組vec1[n1/2,…,n1-1]和vec2[0,…,n2-1-n1/2]的中位數(shù)和原來的中位數(shù)相同，圖中紅色方框里是去掉的元素。
注意：在n1
例如vec1 = [1,3,5,7],vec2 = [2,4,6,8], 如果我們要求的是上中位數(shù)，m1 = m2 =1，即3 < 4, 要刪掉vec1的前半段，這里vec1[m1] = 3 要不要刪除呢，我們只要判斷一下3能否可能成為中位數(shù)，假設3是中位數(shù)，不超過3的數(shù)只有3個（1,2,3），總得元素有8個，因此3不可能成為上中位數(shù)，我們可以在vec1中刪除2兩個元素。
如果是求下中位數(shù)，即m1 = m2 = 2，即5 < 6,刪除vec1前半段時要不要刪除5呢？注意到比不超過5的數(shù)有5個，不低于5的數(shù)有4個，因此5有可能成為下中位數(shù)，因此5不能刪除，vec1中只能刪除左邊兩個元素。同理當vec1的個數(shù)是奇數(shù)時，vec1的中位數(shù)永遠不能刪除，即只能刪除vec1的n1/2（整數(shù)除法）個元素
3、如果vec1[m1] > vec2[m2] ，同上分析，中位數(shù)只可能出現(xiàn)在vec1的前半段或vec2的后半段。如下圖所示，兩個數(shù)組分別去掉n1/2個元素后，子數(shù)組vec1[0,…,n1/2-1]和vec2[n1/2,…,n2-1]的中位數(shù)和原來的中位數(shù)相同
子數(shù)組遞歸求解，即可求出中位數(shù)，算法復雜度為O(log(n1+n2)).注意一下遞歸結(jié)束條件和邊界處理。
int findMedian_logn(int vec1[], int n1, int vec2[], int n2){int m1 = (n1-1) / 2, m2 = (n2-1) / 2;if(n1 == 1){//遞歸結(jié)束條件if(n2 == 1)return vec1[0] < vec2[0] ? vec1[0] : vec2[0];if(n2 % 2 == 0){if(vec1[0] >= vec2[m2+1])return vec2[m2+1];else if(vec1[0] <= vec2[m2])return vec2[m2];else return vec1[0];}else{if(vec1[0] >= vec2[m2])return vec2[m2];else if(vec1[0] <= vec2[m2-1])return vec2[m2-1];else return vec1[0];}}else if(n2 == 1){//遞歸結(jié)束條件if(n1 % 2 == 0){if(vec2[0] >= vec1[m1+1])return vec1[m1+1];else if(vec2[0] <= vec1[m1])return vec1[m1];else return vec2[0];}else{if(vec2[0] >= vec1[m1])return vec1[m1];else if(vec2[0] <= vec1[m1-1])return vec1[m1-1];else return vec2[0];}}else{int cutLen = n1/2 > n2/2 ? n2/2 : n1/2;//注意每次減去短數(shù)組的一半，如果數(shù)組長度n是奇數(shù)，一半是指n-1/2if(vec1[m1] == vec2[m2])return vec1[m1];else if(vec1[m1] < vec2[m2])return findMedian_logn(&vec1[cutLen], n1-cutLen, vec2, n2-cutLen);elsereturn findMedian_logn(vec1, n1-cutLen, &vec2[cutLen], n2-cutLen);}}
算法3：這里我們把問題擴展一下，求兩個有序數(shù)組的第k小的元素。
我們假設這個第k小的元素是X，若X在數(shù)組vec1的第i個位置，如果把X放到vec2中，那么X在排數(shù)組vec2中的第（k-i+1）個位置，則X >= vec2中第k-i個元素 且 X <= vec2中第k-i+1個元素。
因此我們可以首先假設元素X在數(shù)組vec1中，對vec1中的元素進二分查找。
選取vec1中的元素vec1[idx1]（idx1 = n1/(n1+n2)*(k-1), 即第idx1+1個元素，由于不是中位數(shù)，因此不是選取中間元素），看vec2中的元素vec2[idx2]（idx2 = k-idx1-2, 即第k-idx1-1個元素）：
注意到這里的一個不變式：idx1及前面元素的個數(shù) + idx2及前面元素的個數(shù) = k，即（idx1+1）+（idx2+1）= k
如果vec1[idx1] == vec2[idx2] ,剛好有idx1+1+idx2+1 = k個元素不超過vec1[idx1], 則vec1[idx1]為所求
如果vec1[idx1] < vec2[idx2], 不超過vec1[idx1]的元素個數(shù)肯定小于k，因此vec1[idx1]以及其前面的元素肯定小于我們要求的元素；對于vec2[idx2+1]以及其后面的元素，不超過他們的數(shù)的個數(shù)肯定大于K個，因此vec2[idx2+1]以及其后面的元素肯定大于我們要求的元素。
故搜索范圍縮小到vec1[idx1+1,…,n1-1] 和vec2[0...idx2]
如果vec1[idx1] > vec2[idx2], 同理搜索范圍縮小到vec1[0...idx1]和vec2[idx2+1,....n2-1]
其實算法思想和上面的算法2相同。上述算法也可以每次取vec1和vec2的第k/2個元素比較，這樣每次可以使k減小一半。
注意邊界處理。算法中每次迭代平均k都會減小約k/2,因此算法復雜度為O（logk），而k = （n1+n2）/m, m是一個常數(shù)，即復雜度為O（log(n1+n2)）
//找到兩個有序數(shù)組中第k小的數(shù),k>=1int findKthSmallest(int vec1[], int n1, int vec2[], int n2, int k){//邊界條件處理if(n1 == 0)return vec2[k-1];else if(n2 == 0)return vec1[k-1];if(k == 1)return vec1[0] < vec2[0] ? vec1[0] : vec2[0];int idx1 = n1*1.0 / (n1 + n2) * (k - 1);int idx2 = k - idx1 - 2;if(vec1[idx1] == vec2[idx2])return vec1[idx1];else if(vec1[idx1] < vec2[idx2])return findKthSmallest(&vec1[idx1+1], n1-idx1-1, vec2, idx2+1, k-idx1-1);elsereturn findKthSmallest(vec1, idx1+1, &vec2[idx2+1], n2-idx2-1, k-idx2-1);}
算法4：對于尋找兩個有序數(shù)組第k小的元素，還有一種簡化算法1，復雜度為O（k）的算法，在歸并兩個數(shù)組的過程中，如果如果已經(jīng)選擇的元素達到k，就不需要再歸并下去了。
推薦閱讀：
專注服務器后臺技術棧知識總結(jié)分享
歡迎關注交流共同進步