【leetcode】 Median of Two Sorted Arrays

地址

https://leetcode.com/problems/median-of-two-sorted-arrays/description/ ## 题目 ### Median of Two Sorted Arrays 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

题解

看题目时间复杂度可以知道这题是要在两个数组间进行二分。 假设选定i和j满足\(i+j=k\),k代表中位数的位置。 如果\(a[i]<=b[j]\),则中位数不在a数组前i个数中,删除a数列前i个数。反之\(a[i]>b[j]\),同理。证明方法 反证法,自己想想就知道了。 当然删除不是真的删除,打个标记而已,不然时间复杂度炸了。

ps:好久没做题了,想到思路后还写了好久,然后又debug好久,真是丢人。代码写的真是丑陋。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
int n=a.size(),m=b.size(),c=(n+m)&1,k=(n+m+1)/2;
int sa=-1,sb=-1;
n--,m--;
while(1)
{
if(sa==n&&c)
return b[sb+k]*1.0;
else if(sa==n)
return (b[sb+k]+b[sb+k+1])/2.0;
if(sb==m&&c)
return a[sa+k]*1.0;
else if(sb==m)
return (a[sa+k]+a[sa+k+1])/2.0;
if(k==1)
{
if(c)
return min(a[sa+1],b[sb+1])*1.0;
else
{
if(a[sa+1]<b[sb+1])
{
if(sa+2<=n)
return (min(a[sa+2],b[sb+1])+a[sa+1])/2.0;
else
return (a[sa+1]+b[sb+1])/2.0;
}
else
{
if(sb+2<=m)
return (min(a[sa+1],b[sb+2])+b[sb+1])/2.0;
return (a[sa+1]+b[sb+1])/2.0;
}
}
}
int i=min(k/2,n-sa),j=k-i;
if(j>m-sb)
j=m-sb,i=k-j;
if(a[sa+i]<=b[sb+j])
k-=i,sa+=i;
else
k-=j,sb+=j;
}

}
};