题目

题目：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

题目分析

1. 我们要从两个已经排好序的数组里面找出他们的中位数，首先想到就是把两个数组合并到一个有序数组里面，这样我们就可以很容易找出中位数
2. 同时也要考虑元素个数是奇数还是偶数，这样以便于我们判断中位数是直接是数组里面的元素，或者需要我们计算。
3. 对于两个已经排好序的数组进行合并可以参照归并排序法

常规解法

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int i=0,j=0,k=0;
    int* arr=(int*)malloc((nums1Size+nums2Size)*sizeof(int));   //(1)
    while(i<nums1Size&&j<nums2Size){
        arr[k++]=nums1[i]>nums2[j]?nums2[j++]:nums1[i++];
    }
    while(i<nums1Size){
        arr[k++]=nums1[i++];
    }
    while(j<nums2Size){
        arr[k++]=nums2[j++];
    }                                                          //(2)
    int temp=nums1Size+nums2Size;
    if(temp%2!=0){ 
        return arr[temp/2];                                   //(3)
    }
    else{
        return (arr[temp/2]+arr[temp/2-1])*1.0/2;            //(4)
    }
}

(1) 开辟一个数组空间用来存放两个合并后的数组，C语言不支持使用
int nums[nums1Size+nums2Size]来开辟数组
(2)这里是归并排序
(3)如果是奇数直接是我们需要的
(4)如果是偶数，需要计算，不能忘记那个1.0

我们可以看见，在速度上很快 ，但是却很消耗内存
经过多次测试，发现这是一次特殊的，不知道为什么跑这么快

但是事实上我们不需要创建一个新数组，只需要维护两个指针找到数组下标就可以实现，其思想还是来源解法1

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
	int len = nums1Size + nums2Size;
	int p1 = 0, p2 = 0;
	int left = 0, right = 0;
	int i = 0;
	for (i = 0; i <= len / 2; ++i) {
		left = right;
		if (p1 < nums1Size && (p2 >= nums2Size || nums1[p1] < nums2[p2])) {
			right = nums1[p1++];
		}                                 //(1)
		else
			right = nums2[p2++];
	}
	if (len % 2 == 0)
		return (left + right)*1.0 / 2;
	else
		return right;
}

1. 我们需要两个数来标记我们需要的数，其中left表示前一个,right表示当前最小的一个
2. （1）选取最小的在数组nums1的条件是，nums1中还有元素，nums2中没有元素，nums中当前元素大于nums1中当前元素，经过条件判断写成代码形式

PS：做到后面感觉不对劲
经过多次测试

时间波动比较大

进阶解法

我们看到提示中有一个进阶解法，出现log一般都要考虑二分法
这个进阶解法比较复杂，建议点击链接去官网看此解法
不过官网没有给出C的代码，下面我根据解析写出C的代码以供参考。

int getKthNum(int* nums1, int nums1Size, int* nums2, int nums2Size,int k) {
	int p1 = 0, p2 = 0;
	int KthNum = 0;
	while (1) {
		if (p1 == nums1Size)
			return nums2[p2 + k - 1];
		if (p2 == nums2Size)
			return nums1[p1 + k - 1];
		if (k == 1)
			return nums1[p1] > nums2[p2] ? nums2[p2] : nums1[p1];
		int mid = k / 2;
		int newP1 = (p1 + mid> nums1Size?nums1Size:p1+mid) - 1;
		int newP2 = (p2 + mid>nums2Size?nums2Size:p2+mid) - 1;
		int pivot1 = nums1[newP1], pivot2 = nums2[newP2];
		if (pivot1 <= pivot2) {
			k -= (newP1 - p1 + 1);
			p1 = newP1 + 1;
		}
		else {
			k -= (newP2 -p2 + 1);
			p2 = newP2 + 1;
		}
	}

}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
	int len = nums1Size + nums2Size;
	if (len % 2 == 1) {
		int mid = len / 2;
		double median = getKthNum(nums1, nums1Size,nums2, nums2Size, mid+ 1);
		return median;
	}
	else {
		int mid1 = len / 2 - 1, mid2 = len / 2;
		double median = (getKthNum(nums1, nums1Size, nums2, nums2Size, mid1 + 1) + getKthNum(nums1, nums1Size, nums2, nums2Size, mid2 + 1)) / 2.0;
		return median;
	}
}

可以看见这个速度和内存消耗都要比前面两种解法要小。