4. Median of Two Sorted Arrays
題目
https://leetcode.com/problems/median-of-two-sorted-arrays/description/
題意是給出兩個(gè)有序的列表猴蹂，找出它們合并之后的中位數(shù)（如果個(gè)數(shù)為偶數(shù)渡嚣，則是兩個(gè)中位數(shù)的平均數(shù)）。
時(shí)間復(fù)雜度要求是O（log(m+n)）
解題思路
由于這題有時(shí)間復(fù)雜度要求，可以發(fā)現(xiàn)將兩個(gè)列表合并成新列表再使用二分查找是不可行的袁辈。（時(shí)間復(fù)雜度為O（m+n）
所以這題我也是看了題解才有了思路妙黍。
由于兩個(gè)列表 各自是有序的碾篡，我們可以考慮通過(guò)切割列表來(lái)尋找中位數(shù)砍的。考慮同時(shí)切割列表氨肌，一個(gè)切割點(diǎn)為i鸿秆，一個(gè)切割點(diǎn)為j，切割會(huì)把 列表分為[0, i), [i, n) ,[0, j), [j, m) 四個(gè)子列表怎囚，如果能滿(mǎn)足以下條件卿叽，則我們可以快速找到中位數(shù)：
1）i+j = (m+n)/2
2）a[i-1] <= b[j]
3）b[j-1] <= a[i]
這樣我們可以快速找到中位數(shù)為:
奇數(shù)情況下為：
min(a[i], b[j])
偶數(shù)情況下為：
(min(a[i], b[j]) + max(a[i-1], b[j - 1]))/2
示例代碼
class Solution {
public:
int min(int a, int b){
return a < b ? a: b;
}
int max(int a, int b){
return a > b ? a: b;
}
int minelement(int indexa, int indexb, vector<int>& nums1 , vector<int>& nums2){
if(indexa == nums1.size()){
return nums2[indexb];
}
if(indexb == nums2.size()){
return nums1[indexa];
}
return min(nums1[indexa], nums2[indexb]);
}
int maxelement(int indexa, int indexb, vector<int>& nums1 , vector<int>& nums2){
if(indexa == nums1.size()){
return nums2[indexb];
}
if(indexb == nums2.size()){
return nums1[indexa];
}
return max(nums1[indexa], nums2[indexb]);
}
int next(int temp, int tl, int tr){
if(tl +1 == tr ){
if(temp == tl){
return tr;
}else{
return tl;
}
}
return (tl + tr) /2;
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int l1 = nums1.size();
int l2 = nums2.size();
int l = l1 + l2;
int mid = l / 2;
int temp, temp2 = 0;
if(l1 < l2){
nums1.swap(nums2);
l1 = nums1.size();
l2 = nums2.size();
}
if(l2 == 0){
if(l1 % 2 == 0){
return (double) (nums1[l1 / 2] + nums1[l1 / 2 - 1]) /2;
}else{
return (double) nums1[l1 / 2];
}
}
int tl = 0, tr = l1;
temp = (tl + tr) / 2;
while(true){
temp2 = mid - temp;
if(temp > mid){
tr = temp;
temp = next(temp, tl, tr);
continue;
}
if(temp2 > l2){
tl = temp;
temp = next(temp, tl, tr);
continue;
}
if(temp2 == 0){
if(nums1[temp - 1] <= nums2[0]){
break;
}else{
tr = temp;
temp = next(temp, tl, tr);
continue;
}
}else if(temp2 == l2){
if(nums2[temp2 - 1] <= nums1[temp]){
break;
}else{
tl = temp;
temp = next(temp, tl, tr);
continue;
}
}else{
if(nums1[temp - 1] <= nums2[temp2] && nums2[temp2 - 1] <= nums1[temp]){
break;
}else if(nums1[temp - 1] > nums2[temp2]){
tr = temp;
temp = next(temp, tl, tr);
continue;
}else{
tl = temp;
temp = next(temp, tl, tr);
continue;
}
}
}
if( l % 2 == 0){
int s;
if(temp2 == 0){
s = nums1[temp - 1] + minelement(temp, 0, nums1, nums2);
}else if(temp2 == l2){
s = maxelement(temp - 1, l2 - 1, nums1, nums2) + nums1[temp];
}else{
s = maxelement(temp - 1, temp2 - 1, nums1, nums2) + minelement(temp, temp2, nums1, nums2);
}
return (double)s / 2;
}else{
if(temp2 == 0){
return (double) minelement(temp,0, nums1, nums2);
}else if(temp2 == l2){
return (double) nums1[temp];
}else{
return (double) minelement(temp, temp2, nums1, nums2);
}
}
}
};
注意細(xì)節(jié)
- 注意i和j為0或者列表長(zhǎng)度的時(shí)候（這里的corner case很多）
