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è)題目的错忱，第四題儡率，原本以為是一道水題，就是在做的過(guò)程中注意一下邊界條件的處理就可以了的題呢以清，但是當(dāng)我看到需要考慮時(shí)間復(fù)雜度的時(shí)候儿普，我瞬間就蒙了，因?yàn)闀r(shí)間復(fù)雜度要求是log級(jí)別的掷倔，就是相當(dāng)于告訴我們眉孩，不能把兩個(gè)數(shù)組直接合并成一個(gè)數(shù)組了。所以勒葱，這題的難度一下子就上來(lái)了浪汪，后來(lái)查了點(diǎn)資料，先把答案曬出來(lái)吧凛虽，然后再慢慢解釋?zhuān)瑸槭裁匆@么做：
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int total = nums1.length+nums2.length;
if(total%2==0){
return (findKth(total/2+1, nums1, nums2, 0, 0)+findKth(total/2, nums1, nums2, 0, 0))/2.0;
}else{
return findKth(total/2+1, nums1, nums2, 0, 0);
}
}
public int findKth(int k, int[] nums1, int[] nums2, int s1, int s2){
if(s1>=nums1.length)
return nums2[s2+k-1];
if(s2>=nums2.length)
return nums1[s1+k-1];
if(k==1)
return Math.min(nums1[s1], nums2[s2]);
int m1 = s1+k/2-1;
int m2 = s2+k/2-1;
int mid1 = m1<nums1.length?nums1[m1]:Integer.MAX_VALUE;
int mid2 = m2<nums2.length?nums2[m2]:Integer.MAX_VALUE;
if(mid1<mid2){
return findKth(k-k/2, nums1, nums2, m1+1, s2);
}else{
return findKth(k-k/2, nums1, nums2, s1, m2+1);
}
}
}
好了死遭，整個(gè)答案就是這個(gè)樣子的，其實(shí)這個(gè)問(wèn)題凯旋，我們是可以把它進(jìn)行轉(zhuǎn)換的呀潭，我說(shuō)一下轉(zhuǎn)換的步驟，大家就應(yīng)該明白了至非。
1.找一個(gè)數(shù)組中最大數(shù)和最小數(shù)的問(wèn)題钠署，最笨的方法是，先排序睡蟋，然后返回最大值踏幻，最小值。
2.稍微優(yōu)化一點(diǎn)的算法就是一個(gè)循環(huán)下來(lái)掃描戳杀，采用動(dòng)態(tài)規(guī)劃的算法该面，將最大值，最小值求出來(lái)信卡。
3.可以采用建堆的方式隔缀，說(shuō)到這想必大家應(yīng)該能明白了，就是建立一個(gè)大根堆傍菇，或者一個(gè)小根堆猾瘸，然后從找找到相應(yīng)位置的東西即可。
4.我們采用的是第四種丢习，是一個(gè)類(lèi)似于快排的方式牵触，每次我們都隨機(jī)將一組數(shù)分成兩個(gè)部分，然后采用同樣的方法咐低，每次都可以隨機(jī)的丟棄數(shù)列中的一部分揽思，這樣之后我們就可以舍棄很多數(shù)據(jù)了。
然后我們這個(gè)題见擦，采用的就是大概第四種方法：
思想大概就是上面這種方式叫胁，每次都可以舍棄很大的一個(gè)部分。然后采用遞歸的方式书劝。
