原題鏈接Median of Two Sorted Arrays

意思是給定兩個有序序列，找到合并之后的中位數，要求復雜度O(log(m+n))。擴展方面，找到合并之后第K小的數，因為中位數也符合第K小范疇，所以直接按照后者解題即可

---

不考慮復雜度的情況下，首先想到的方法是一次從兩個數組中選取較小的那個，直到選取第k個，此種方法復雜度在O(k)，代碼如下

class Solution { public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int lhs_idx = 0;int rhs_idx = 0;/* 奇數偶數時中位數計算方法不同 */int total = nums1.size() + nums2.size();if(total % 2 == 0){return (findKth(nums1, nums2, total / 2) + findKth(nums1, nums2, total / 2 + 1)) / 2.0;}else{return findKth(nums1, nums2, total / 2 + 1) / 1.0;}}int findKth(vector<int>& nums1, vector<int>& nums2, int k){int ans = 0;int lhs_idx = 0;int rhs_idx = 0;/* 復雜度體現處，遍歷k次，所以為O(k) */while(k--){/* 需要考慮邊界情況 */if(lhs_idx >= nums1.size() && rhs_idx < nums2.size())ans = nums2[rhs_idx++];else if(lhs_idx < nums1.size() && rhs_idx >= nums2.size())ans = nums1[lhs_idx++];else if(lhs_idx >= nums1.size() && rhs_idx >= nums2.size())return -1;else if(nums1[lhs_idx] < nums2[rhs_idx])ans = nums1[lhs_idx++];elseans = nums2[rhs_idx++]; }return ans;}};

---

接下來想辦法達到O(log(m+n))，涉及到log通常會考慮二分法，所以優化需要在findKth()函數中采用二分法計算。下面把nums1看成數組A，nums2看成數組B，A的大小為m，B的為n
既然需要找到第K小的數，那么首先考慮A的第k/2個元素和B的第k/2個元素。這么考慮是因為

• 既然采用二分法，那么使用時通過二分就一定可以把結果的范圍縮小

具體說明，
如果A[k/2] > B[k/2]，說明B的前k/2個元素在合并A,B之后的前k個位置

• 因為A[k/2]] > B[k/2]，那么假設A[i] == B[k/2]，i一定小于k/2，顯然此時A的前i個，B的前k/2個元素一定都是組成合并之后前k小元素的成員，所以B的前k/2個元素一定都是前k個元素的成員
• 所以此時就已經找到了k/2個元素了，只需再找k/2個最小的元素即可，而這些元素都在B的[k/2, n)和A中，很明顯可以利用遞歸，此時k改為k/2

如果A[k/2] <= B[k/2]，在A的[k/2,m)和B中查找剩下的k/2個元素，原理同上

代碼如下

class Solution { public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();int total = m + n;if(total % 2 == 0){return (findKth(nums1, nums2, total / 2) + findKth(nums1, nums2, total / 2 + 1)) / 2.0;}else{return findKth(nums1, nums2, total / 2 + 1) / 1.0;}}int findKth(vector<int> A, vector<int> B, int k){/* 總是讓A的大小小于B */if(A.size() > B.size())return findKth(B, A, k);if(A.size() == 0)return B[k - 1];if(k == 1)return std::min(A[0], B[0]);int m = A.size();int n = B.size();/* 如果大小不足k/2，取自身大小 *//* 因為有這種情況，后面不一定是k/2，所以遞歸調用時是k - j/k - i */int i = std::min(m, k / 2);int j = std::min(n, k / 2);if(A[i - 1] > B[j - 1]){return findKth(A, std::vector<int>(B.begin() + j, B.end()), k - j);}else{return findKth(std::vector<int>(A.begin() + i, A.end()), B, k - i);}} };

準確說這種方法沒有達到O(log(m+n))，但是更具通用性，可以計算不僅僅是中位數，還可以計算第k小元素，效率相對更高。

不過就本題而言，每次二分AB中間的位置，根據大小關系拋棄小方的左端以及大方同樣長度的右端，以達到最后的結果，但是沒有什么通用性，只可以計算中位數

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----两个有序数组合并后的第K个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。