題目
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è)有序數(shù)列合成一個(gè)有序數(shù)列的話(huà)需要O(n+m)的時(shí)間蛮浑，所以考慮不合成的方法伦吠。
很自然思考兩個(gè)數(shù)列的中位數(shù)與最終的中位數(shù)之間的關(guān)系湿蛔。
假設(shè)數(shù)列{a_n}共有na個(gè)數(shù)且中位數(shù)為A，數(shù)列{b_n}共有nb個(gè)數(shù)且中位數(shù)為B默蚌。
那么不考慮整除的情況下冰沙，A的左右各有(na-1)/2個(gè)數(shù)架诞，B的左右各有(nb-1)/2個(gè)數(shù)闪金。通過(guò)比較A和B的大小，可以確定A和B之間的兩組數(shù)字瞳腌。一開(kāi)始覺(jué)得這樣就將問(wèn)題問(wèn)題轉(zhuǎn)化為一個(gè)規(guī)模為原來(lái)一半的子問(wèn)題绞铃，并且時(shí)間復(fù)雜度可以滿(mǎn)足題意。
但是后來(lái)發(fā)現(xiàn)不對(duì)嫂侍，因?yàn)闊o(wú)法保證新得到的子問(wèn)題位于原問(wèn)題的正中央儿捧。所以需要增加約束，希望每次取左右兩邊的值的時(shí)候可以盡量使子問(wèn)題往中間靠吵冒。但是這樣一來(lái)時(shí)間復(fù)雜度又變?yōu)镺(log(n)+log(m))纯命，即O(log(nm))，不滿(mǎn)足題意痹栖。
在經(jīng)歷了漫長(zhǎng)的掙扎之后還是決定看題解……
題解也是取兩個(gè)數(shù)組中的某些數(shù)字進(jìn)行比較，但是沒(méi)有選擇中間的數(shù)瞭空，而是選擇了第k/2個(gè)數(shù)揪阿，這樣來(lái)描述問(wèn)題自由度更高。通過(guò)比較兩個(gè)數(shù)組中的第k/2個(gè)數(shù)的大小來(lái)逐步縮小范圍咆畏，從而得到整體的第k個(gè)數(shù)南捂，最終得到中位數(shù)。
實(shí)現(xiàn)
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m=nums1.size();
int n=nums2.size();
vector<int>::iterator A=nums1.begin();
vector<int>::iterator B=nums2.begin();
int k=m+n;
if(k&0x01)
return findKth(A, m, B, n, k/2+1);
else
return (findKth(A, m, B, n, k/2)+findKth(A, m, B, n, k/2+1))/2.0;
}
private:
static double findKth(const vector<int>::iterator & A, int m,
const vector<int>::iterator & B, int n, int k){
if(m>n) return findKth(B, n, A, m, k);
if(m==0)return B[k-1];
if(k==1) return min(A[0], B[0]);
int ia=min(m, k/2), ib=k-ia;
if(A[ia-1]<B[ib-1])
return findKth(A+ia, m-ia, B, n, k-ia);
else if(A[ia-1]>B[ib-1])
return findKth(A, m, B+ib, n-ib, k-ib);
else
return A[ia-1];
}
};
沒(méi)有太多好說(shuō)的旧找，基本上就是默寫(xiě)題解溺健。。钮蛛。
思考
本段代碼中幾處地方比較巧妙：
- 假定m<n的處理
- 對(duì)于m<k/2的處理
