# 引言
题目链接：https://leetcode.com/problems/median-of-two-sorted-arrays/description/
# 题目大意
给出两个升序的有序序列，找到两个序列合并后序列的中位数
Hint: You may assume nums1 and nums2 cannot be both empty.
官方希望复杂度为 O(log(m+n))
# 题解
对于一个长度为 n 的已排序数列 nums ,
若 n 为奇数，中位数为 nums[n/2]
若 n 为偶数，则中位数 (nums[n/2-1] + nums[n/2]) / 2
# 方法一
# 一句话题解
走一次归并排序逻辑 (先确定中位数下标过程中注意计算即可)
复杂度 O(m+n) , (明显和官方要求复杂度不是一个级别，目测后台数据比较水所以过了)
# 方法二
转换为寻找第 k 大的数据，类似于快排递归调整数据使得左边所有数据小于当前数据，右边大于等于当前数据这一步骤
详解
假设 nums1 和 nums2 数组中元素个数都是大于 k/2 的，且从 0 开始编号，比较 a = nums1[k/2-1] 和 b = nums2[k/2-1]
- 如果 a < b 那么
nums1[0]到nums1[k/2-1]这k/2个数在合并后的有序数组中，一定在第 k 小的数左边 ————nums1数组中比 a 小的数一共是k/2-1个。nums2数组中比 a 小的数最多有k/2-1个。因而合并后比 a 小的数最多有 k/2-1+k/2-1 < k-2, 即 a 最多是第 k-1 小的数。因此 nums1 数组前 k/2 个数可以剔除了 - 如果 a > b 同理，剔除掉 nums2 数组前 k/2 个数
- 如果 a = b, a 即为所求
实际中若 nums1 和 nums2 数组中元素个数不足 k/2 个的话，只需要前两者分割数据个数等于 k 即可
复杂度：每次剔除掉 k 一半个元素，即时间复杂度是 O(logk) , 对于此题， k=(m+n)/2 即复杂度 O(log(m+n))
# AC 代码
c++ 版本一 (归并排序法，也是博主 AC 方法，为了不使用额外空间代码写得很挫，不够优雅)
class Solution
{
public:
double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
{
int total = nums1.size() + nums2.size();
if (0 == total)
{
return 0;
}
if (2 == total)
{
if (0 == nums1.size())
{
return (nums2[0] + nums2[1]) * 1.0 / 2;
}
if (0 == nums2.size())
{
return (nums1[0] + nums1[1]) * 1.0 / 2;
}
return (nums1[0] + nums2[0]) * 1.0 / 2;
}
double medianNumSum = 0;
int medianNum1Index = ((total + 1) >> 1) - 1;
int medianNum2Index = total >> 1;
int i = 0;
int j = 0;
for (; i < nums1.size() && j < nums2.size();)
{
if (nums1[i] < nums2[j])
{
++i;
}
else
{
++j;
}
if (i + j == medianNum1Index && i < nums1.size() && j < nums2.size())
{
medianNumSum += (nums1[i] < nums2[j] ? nums1[i] : nums2[j]);
}
if (i + j == medianNum2Index && i < nums1.size() && j < nums2.size())
{
medianNumSum += (nums1[i] < nums2[j] ? nums1[i] : nums2[j]);
}
}
if (i + j <= medianNum2Index && i < nums1.size())
{
for (; i < nums1.size(); ++i)
{
if (i + j == medianNum1Index)
{
medianNumSum += nums1[i];
}
if (i + j == medianNum2Index)
{
medianNumSum += nums1[i];
}
}
}
if (i + j <= medianNum2Index && j < nums2.size())
{
for (; j < nums2.size(); ++j)
{
if (i + j == medianNum1Index)
{
medianNumSum += nums2[j];
}
if (i + j == medianNum2Index)
{
medianNumSum += nums2[j];
}
}
}
return medianNumSum / 2;
}
};
c++ 版本二
class Solution | |
{ | |
public: | |
double findKthValue(vector<int> &nums1, vector<int> &nums2, int start1, int len1, int start2, int len2, int k) | |
{ | |
if (len1 > len2) | |
{ | |
return findKthValue(nums2, nums1, start2, len2, start1, len1, k); | |
} | |
if (0 == len1) | |
{ | |
return nums2[start2 + k - 1]; | |
} | |
if (1 == k) | |
{ | |
return nums1[start1] < nums2[start2] ? nums1[start1] : nums2[start2]; | |
} | |
int p = k / 2 < len1 ? k / 2 : len1; | |
int q = k - p; | |
if (nums1[start1 + p - 1] > nums2[start2 + q - 1]) | |
{ | |
return findKthValue(nums1, nums2, start1, len1, start2 + q, len2 - q, k - q); | |
} | |
else if (nums1[start1 + p - 1] < nums2[start2 + q - 1]) | |
{ | |
return findKthValue(nums1, nums2, start1 + p, len1 - p, start2, len2, k - p); | |
} | |
else | |
{ | |
return nums1[start1 + p - 1]; | |
} | |
} | |
double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) | |
{ | |
int total = nums1.size() + nums2.size(); | |
if (total & 1) | |
{ | |
return findKthValue(nums1, nums2, 0, nums1.size(), 0, nums2.size(), (total >> 1) + 1); | |
} | |
else | |
{ | |
return (findKthValue(nums1, nums2, 0, nums1.size(), 0, nums2.size(), total >> 1) + | |
findKthValue(nums1, nums2, 0, nums1.size(), 0, nums2.size(), (total >> 1) + 1)) / 2; | |
} | |
} | |
}; |
go 版本
func findKthValue(nums1, nums2 []int, start1, len1, start2, len2, k int) float64 { | |
if len1 > len2 { | |
return findKthValue(nums2, nums1, start2, len2, start1, len1, k) | |
} | |
if 0 == len1 { | |
return float64(nums2[start2+k-1]) | |
} | |
if 1 == k { | |
return math.Min(float64(nums1[start1]), float64(nums2[start2])) | |
} | |
var p, q int | |
if k/2 < len1 { | |
p = k / 2 | |
} else { | |
p = len1 | |
} | |
q = k - p | |
if nums1[start1+p-1] > nums2[start2+q-1] { | |
return findKthValue(nums1, nums2, start1, len1, start2+q, len2-q, k-q) | |
} else if nums1[start1+p-1] < nums2[start2+q-1] { | |
return findKthValue(nums1, nums2, start1+p, len1-p, start2, len2, k-p) | |
} else { | |
return float64(nums1[start1+p-1]) | |
} | |
} | |
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { | |
lens := len(nums1) + len(nums2) | |
if 1 == lens&1 { | |
return findKthValue(nums1, nums2, 0, len(nums1), 0, len(nums2), lens/2+1) | |
} else { | |
return (findKthValue(nums1, nums2, 0, len(nums1), 0, len(nums2), lens/2) + | |
findKthValue(nums1, nums2, 0, len(nums1), 0, len(nums2), lens/2+1)) / 2 | |
} | |
} |
