文章目录
1题目理解
输入：2个已经排序号的int数组nums1,nums2
输出：这两个数组合并后的中位数
要求：m是nums1的长度，n是nums2的长度。时间复杂度应该是O(log(m+n))。
例子:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
2 二分查找解题
这道题目如果不要求时间复杂度的话，很简单。把两个数组合并。如果长度为奇数，找到中间位置的下标返回该元素。如果长度是偶数，则找到中间两个元素，求平均值返回。要符合时间复杂度要求就要用二分。以下内容来源于力扣，只看解法四。
这种解法在一刷的时候没看明白，现在二刷更清楚了。知道怎么从题目描述，到最终的条件。知道为什么这样做是对的。
2.1中位数的定义
中位数将一个数组分成两部分，左边元素个数等于右边元素个数，并且左边元素的值都小于右边元素的值。
2.2 数组切分
在数组中，我们在任意位置i，将数组切分为2部分。
由于数组A中有m个元素，所以数组A有m+1种切分方法。
i
∈
[
0
,
m
]
i\in[0,m]
i∈[0,m],那么
l
e
n
(
l
e
f
t
A
)
=
i
,
l
e
n
(
r
i
g
h
t
A
)
=
m
−
i
len(left_A)=i,len(right_A)=m-i
len(leftA)=i,len(rightA)=m−i
采用同样的方式，在位置j，将数组B切分为两部分。
j
∈
[
0
,
n
]
j\in[0,n]
j∈[0,n],那么
l
e
n
(
l
e
f
t
B
)
=
j
,
l
e
n
(
r
i
g
h
t
B
)
=
n
−
j
len(left_B)=j,len(right_B)=n-j
len(leftB)=j,len(rightB)=n−j
将left_A和left_B一起合并形成left_part，将right_A和right_B一起合并形成right_part。
当A和B的长度是偶数的时候，如果len(left_part)=len(right_part)，并且max(left_part)<=min(right_part)，
那么
中
位
数
=
m
a
x
(
l
e
f
t
_
p
a
r
t
)
+
m
i
n
(
r
i
g
h
t
_
p
a
r
t
)
2
中位数=\dfrac{max(left\_part)+min(right\_part)}{2}
中位数=2max(left_part)+min(right_part)
当A和B的长度是奇数的时候，如果len(left_part)=len(right_part)+1，并且max(left_part)<=min(right_part)，那么
中
位
数
=
m
a
x
(
l
e
f
t
_
p
a
r
t
)
中位数=max(left\_part)
中位数=max(left_part)
2.3分析条件
对于奇偶情况不同，长度条件不一样，我们可以做合并。要想得到中位数需要符合上面两个条件。这两个条件可以这样理解。
1 i+j=m-i+n-j (m+n为偶数)或者 i+j=m-i+n-j+1(m+n为奇数)。等号左侧是前一部分元素个数，等号右侧是后一部分元素个数。将i，j都转到等号左边，做变换，得到
i
+
j
=
m
+
n
+
1
2
i+j=\dfrac{m+n+1}{2}
i+j=2m+n+1。
具体过程是，m+n为偶数,对于i+j=m-i+n-j ,得到2*(i+j)=m+n，进一步
i
+
j
=
m
+
n
2
i+j=\dfrac{m+n}{2}
i+j=2m+n，因为m+n为偶数，其实
m
+
n
2
=
m
+
n
+
1
2
\dfrac{m+n}{2}=\dfrac{m+n+1}{2}
2m+n=2m+n+1。因为这里取的是整除，所以+1不会影响结果。例如
4
2
=
2
{\dfrac{4}{2}=2}
24=2,4+1=5，
5
2
=
2
{\dfrac{5}{2}=2}
25=2。所以此时，
i
+
j
=
m
+
n
+
1
2
i+j=\dfrac{m+n+1}{2}
i+j=2m+n+1
m+n为奇数, i+j=m-i+n-j+1,得到2*(i+j)=m+n+1,进一步得到
i
+
j
=
m
+
n
+
1
2
i+j=\dfrac{m+n+1}{2}
i+j=2m+n+1。
所以条件1就是
i
+
j
=
m
+
n
+
1
2
i+j=\dfrac{m+n+1}{2}
i+j=2m+n+1
2 0 < = i < = m 0<=i<=m 0<=i<=m, 0 < = j < = n 0<=j<=n 0<=j<=n。如果我们规定m<=n，那么对于任意的 i ∈ [ 0 , m ] i \in[0,m] i∈[0,m],都有 j = m + n + 1 2 − i ∈ [ 0 , n ] j=\dfrac{m+n+1}{2}-i \in[0,n] j=2m+n+1−i∈[0,n]。这是因为不能让j是负数。可以举一个反例。例如m=10,n=4,当i=9的时候，j=7-9就是负数了。
3 max(left_part)<=min(right_part)，的等价条件是A[i-1]<=B[j]并且B[j-1]<=A[i]。我们可以对该条件做进一步分析。
首先因为数组切分可能切在数组开始，也可能切在数组末尾。也就是说i=0，也有i=m,j=0,j=n的情况。这个时候我们假设A[-1]=B[-1]=
−
∞
-\infty
−∞，A[m+1]=B[n+1]=
∞
\infty
∞。这样可以保证结果值不受影响。如果i=0，那么
l
e
f
t
A
=
−
∞
left_A={-\infty}
leftA=−∞，最大值肯定来源于
l
e
f
t
B
left_B
leftB。所以结果不影响。其他同理。
接着，我们需要证明A[i-1]<=B[j]并且B[j-1]<=A[i] 等价于，找到最大的i使得A[i-1]<=B[j]，
j
=
m
+
n
+
1
2
−
i
j=\dfrac{m+n+1}{2}-i
j=2m+n+1−i。
这是因为当i从0到m主键增加，j会从n到0逐渐减小，A[i-1]递增，B[j]逐渐递减。总会找到一个最大的i，使得A[i-1]<=B[j]。
如果i是最大的，那说明i+1不满足，说明A[i]>B[j-1]，也就是说B[j-1]<A[i]。和原来的条件要求是一样的。
因此，我们可以在[0,m]上找到最大的i，使得A[i-1]<=B[j],那么i,j就是切分点。前一部分元素的最大值，以及后一部分的最小值，才可能是数组的中位数。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
if(m>n){
return findMedianSortedArrays(nums2,nums1);
}
int l = 0, r =m;
int median1=0,median2=0;
while(l<=r){
int i = (l+r)>>1;
int j = (m+n+1)/2-i;
int leftA = (i>0?nums1[i-1]:Integer.MIN_VALUE);
int rightA = (i<m?nums1[i]:Integer.MAX_VALUE);
int leftB = (j>0?nums2[j-1]:Integer.MIN_VALUE);
int rightB = (j<n?nums2[j]:Integer.MAX_VALUE);
if(leftA<=rightB){
median1 = Math.max(leftA,leftB);
median2 = Math.min(rightA,rightB);
l = i+1;
}else{
r = i-1;
}
}
return (m+n)%2==0?(median1+median2)/2.0:median1;
}
}