​ 最近刚开始刷Leetcode，第一道Hard题就难倒了我。题解里有位大神的算法很巧妙，我很容易就理解了，在此做个记录。

题目链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

题解链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/

题目

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3] nums2 = [2]

则中位数是 2.0 示例 2:

nums1 = [1, 2] nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

分析

首先要理解中位数

中位数（Median）又称中值，统计学中的专有名词，是按顺序排列的一组数据中居于中间位置的数，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，通常取最中间的两个数值的平均数作为中位数。

[2 3 5] 中位数是3

[1 4 7 9] 中位数是(4+7)/2=5.5

割(Cut)的概念

• 通过切一刀，可以把有序数组分成左右两个部分，切的那一刀就被称为割(Cut)。

• 割(Cut)的左右会有两个元素，分别是左边最大值和右边最小值。

• 定义LMax= Max(LeftPart) RMin = Min(RightPart) //由小到大的有序数组

• 割可以割在2个数中间，也可以割在1个数上，如果割在一个数上，那么这个数既属于左边，也属于右边

奇数组: [2 3 5] 对应的中位数为3，假定割(Cut)在3上，我们可以把3分为2个： [2（3/3） 5]

因此LMax=3, RMin=3

偶数组: [1 4 7 9] 对应的中位数为 (4 + 7) /2 = 5.5,假定割(Cut)在4和7之间： [1 （4/7）9]

因此LMax=4, RMin=7

割和第k个元素

一个数组

对于有序数组A，如果在k的位置割一下，容易得出LMax = RMin = A[k]

两个数组

将两个数组合成一个有序数组时，第k位的元素

我们设: Ci为第 i个数组的割

LMaxi为第i个数组割后的左元素i

RMini为第i个数组割后的右元素

首先，因为数组是有序的，所以LMax1 <= RMin1，LMax2 <= RMin2 //割在某个数上时左右相等

其次，如果让LMax1 <= RMin2，LMax2 <= RMin1 呢？

这表示左半边全部小于右半边。如果让左边的元素个数相加刚好为k，那第k个元素就是max(LMax1, Lmax2)，也就是合并后有序数组左边k个元素的最大值。

那么如果LMax1 > RMin2，说明数组1的左边元素太多，我们把C1减小，C2 = k - C1相应地增大。LMax2 > RMin1同理，把C2减小，C1 = k - C2也就相应地增大。

举例（设k = 3）

[2 3 5] [1 4 7 9]

设C1 = 1，则 C2 = k - C1 = 2 割后：

[2 3 / 5] [1 / 4 7 9]

此时，LMax1 = 3, RMin1 = 5, LMax2 = 1, RMin2 = 4,

满足 LMax1 < RMin2 且 LMax2 < RMin1 ，

所以第3个元素为max(LMax1, LMax2) = 3

两个数组合并后的长度问题 （本篇题解巧妙所在）

两个数组的最大问题是，它们合并后，m+n总数可能为奇, 也可能为偶，所以我们得想法让m+n总是为偶数

通过虚拟加入‘#’，我们让m转换成2m+1 ，n转换成2n+1, 两数之和就变成了2m+2n+2，恒为偶数。

注意是虚拟加，其实根本没这一步，通过下面的转换，我们可以保证虚拟加后每个元素跟原来的元素一一对应

这么虚拟加后，每个位置可以通过/2得到原来元素的位置：

比如 2，原来在0位，现在是1位，1/2=0

比如 3，原来在1位，现在是3位，3/2=1

比如 5，原来在2位，现在是5位，5/2=2

比如 9，原来在3位，现在是7位，7/2=3

而对于割(Cut)，如果割在‘#’上等于割在2个元素之间，割在数字上等于把数字划到2个部分，总是有以下成立：

LMaxi = (Ci-1)/2 位置上的元素 RMini = Ci/2 位置上的元素

例如：

割在3上，C = 3，LMax=a[(3-1)/2]=A[1]，RMin=a[3/2] =A[1]，刚好都是3的位置！

割在4/7之间‘#’，C = 4，LMax=A[(4-1)/2]=A[1]=4 ，RMin=A[4/2]=A[2]=7

剩下的事情就好办了，把2个数组看做一个虚拟的数组A，A有2m+2n+2个元素，割在m+n+1处，所以我们只需找到m+n+1位置的元素和m+n+2位置的元素就行了。

左边：A[m+n+1] = Max(LMax1,LMax2)

右边：A[m+n+2] = Min(RMin1,RMin2)

==>Mid = (A[m+n+1]+A[m+n+2])/2 = (Max(LMax1,LMax2) + Min(RMin1,RMin2) )/2

最快的割(Cut)是使用二分法，有2个数组，我们对哪个做二分呢？

根据之前的分析，我们知道了，只要C1或C2确定，另外一个也就确定了。这里，为了效率，我们肯定是选长度较短的做二分，假设为C1。

LMax1>RMin2，把C1减小，C2增大。—> C1向左二分

LMax2>RMin1，把C1增大，C2减小。—> C1向右二分

如果C1或C2已经到头了怎么办？

这种情况出现在：如果有个数组完全小于或大于中值。假定n<m, 可能有4种情况：

C1 = 0 —— 数组1整体都在右边了，所以都比中值大，中值在数组2中，简单的说就是数组1割后的左边是空了，所以我们可以假定LMax1 = INT_MIN

C1 =2n —— 数组1整体都在左边了，所以都比中值小，中值在数组2中 ，简单的说就是数组1割后的右边是空了，所以我们可以假定RMin1= INT_MAX，来保证LMax2 < RMin1恒成立

C2 = 0 —— 数组2整体在右边了，所以都比中值大，中值在数组1中 ，简单的说就是数组2割后的左边是空了，所以我们可以假定LMax2 = INT_MIN C2 = 2m —— 数组2整体在左边了，所以都比中值小，中值在数组1中, 简单的说就是数组2割后的右边是空了，为了让LMax1 < RMin2 恒成立，我们可以假定RMin2 = INT_MAX

代码

 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
49
50
51
52

#include <stdio.h>
#include <vector>
using namespace std;

#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))

class Solution {
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int n = nums1.size();
		int m = nums2.size();

		if (n > m)  //保证数组1一定最短
		{
			return findMedianSortedArrays(nums2, nums1);
		}
	
		// Ci 为第i个数组的割,比如C1为2时表示第1个数组只有2个元素。LMaxi为第i个数组割后的左元素。RMini为第i个数组割后的右元素。
		int LMax1, LMax2, RMin1, RMin2, c1, c2, lo = 0, hi = 2 * n;  //我们目前是虚拟加了'#'所以数组1是2*n长度
	
		while (lo <= hi)   //二分
		{
			c1 = (lo + hi) / 2;  //c1是二分的结果
			c2 = m + n - c1;
	
			LMax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
			RMin1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2];
			LMax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
			RMin2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];
	
			if (LMax1 > RMin2)
				hi = c1 - 1;
			else if (LMax2 > RMin1)
				lo = c1 + 1;
			else
				break;
		}
		return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;
	}
};


int main(int argc, char *argv[])
{
	vector<int> nums1 = { 2,3, 5 };
	vector<int> nums2 = { 1,4,7, 9 };
	
	Solution solution;
	double ret = solution.findMedianSortedArrays(nums1, nums2);
	return 0;
}