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)).
有兩個(gè)有序的數(shù)組num1和num2,容量分別為m,n茬底。找到兩個(gè)數(shù)組的中位數(shù)棠赛。整個(gè)的時(shí)間復(fù)雜度應(yīng)該為O(log(m+n)).
解：
求中位數(shù)，則應(yīng)該分別考慮m+n的 奇偶性嗤谚，然后調(diào)用一個(gè)函數(shù)舆床，返回兩個(gè)向量合并成一個(gè)有序序列缕粹，的第k個(gè)值登夫。
接下來(lái)我們主要的任務(wù)就是寫出這個(gè)函數(shù)。
我們不妨設(shè)n<=m,因?yàn)閮蓚€(gè)數(shù)組可以互換順序，不影響結(jié)果董栽。我們?cè)?strong>num1數(shù)組中找到第p=min(k/2,n)個(gè)數(shù)a码倦，在num2中找到第k-p的數(shù)b。相比較：如果a>b,那么我們可以確定我們最終要找的數(shù)載b之后锭碳，則我們重新確定num2數(shù)組（去掉包括b之前的元素）袁稽，遞歸尋找第k-p個(gè)數(shù)，反之同理工禾。這事我們?cè)俅_定結(jié)束條件运提，當(dāng)其中一個(gè)數(shù)組為空的時(shí)候，直接返回另一個(gè)數(shù)組第k個(gè)數(shù)闻葵。當(dāng)k等于1的時(shí)候返回min(num1[0],num[0])。
代碼如下(C++)：
class Solution { public: //尋找兩個(gè)數(shù)組如果合并為一個(gè)有序數(shù)組之后的第k個(gè)數(shù)癣丧。 int ans(vector<int>& nums1,vector<int>& nums2,int k){ int n = nums1.size(); int m = nums2.size(); if(n > m){ return ans(nums2,nums1,k); } if(n == 0) return nums2[k-1]; if(k == 1) return min(nums1[0],nums2[0]); int pa = min(k/2,n),pb = k - pa; if(nums1[pa - 1] < nums2[pb - 1] ){ vector<int> a(nums1.begin() + pa, nums1.end()); return ans(a,nums2,k - pa); } else if(nums1[pa - 1] > nums2[pb - 1]){ vector<int> b(nums2.begin() + pb,nums2.end()); return ans(nums1,b,k - pb); } else return nums1[pa-1]; } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int n = nums1.size(); int m = nums2.size(); int k = (n + m)/2; if((m + n)%2){ return ans(nums1,nums2,k + 1); } else { return (ans(nums1,nums2,k) + ans(nums1,nums2,k+1))/2.0; } }
時(shí)間復(fù)雜度因?yàn)橥ㄟ^(guò)遞歸槽畔，為O(log(m+n))。
空間復(fù)雜度為O(1)胁编。
