目录
- 题目
- 题目分析
- 常规解法
- 进阶解法
题目
题目：给定两个大小分别为 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)) 的算法解决此问题吗？
题目分析
- 我们要从两个已经排好序的数组里面找出他们的中位数，首先想到就是把两个数组合并到一个有序数组里面，这样我们就可以很容易找出中位数
- 同时也要考虑元素个数是奇数还是偶数，这样以便于我们判断中位数是直接是数组里面的元素，或者需要我们计算。
- 对于两个已经排好序的数组进行合并可以参照归并排序法
常规解法
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;
}
- 我们需要两个数来标记我们需要的数，其中left表示前一个,right表示当前最小的一个
- （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;
}
}
可以看见这个速度和内存消耗都要比前面两种解法要小。