题目链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/description/
给定两个大小为 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
题解：
考虑转化为求两个有序数组的第 $k$ 小数，
不妨先假设两个有序数组的长度都是大于等于 $c = leftlfloor {frac{k}{2}} ight floor$ 的，比较 $A[c]$ 和 $B[c]$，有两种情况：
1、$A[c] le B[c]$，那么两个数组合并之后，若 $B[1] sim B[c]$ 的位置越往前靠，相应的 $A[c]$ 就越会往后靠，但显然 $B[c]$ 所在位置的最靠前情况是在第 $2c le k$ 个，那么 $A[c]$ 所在位置的最差情况就是在第 $2c-1 le k-1$ 个，因此 $A[1] sim A[c]$ 必然在前 $k-1$ 小的数之中，可以将 $A[1] sim A[c]$ 截去，不影响寻找第 $k$ 小数；
2、$A[c] > B[c]$，类似于情况2，可以将 $B[1] sim B[c]$ 截去。
若两个有序数组的长度存在小于 $c = leftlfloor {frac{k}{2}} ight floor$ 的情况呢？首先可以确定的是，就算存在这种情况，也肯定只有其中一个的长度会小于 $c$，
不妨设是 $A$ 数组的长度小于 $c$，那么，可以比较 $A[A.size]$ 和 $B[k-A.size]$，和上面也是一样的道理。
最后处理边界情况：当 $k=1$ 的时候，返回 $A[1]$ 和 $B[1]$ 中小的那一个即可；当两个数组中有一个为空的时候，就返回另一个数组的第 $k$ 个元素。
时间复杂度：
考虑是不断地让 $k$ 除以 $2$，直到 $k=1$ 时停止，故时间复杂度 $O(log(k)) = O(log(len)) = O(log(m+n))$，满足题目要求。
AC代码：
class Solution { public: int getkth(const vector<int>& nums1,int x,const vector<int>& nums2,int y,int k) { if(x>=nums1.size()) return nums2[y+k-1]; //A数组为空 if(y>=nums2.size()) return nums1[x+k-1]; //B数组为空 if(k==1) return min(nums1[x],nums2[y]); int c1=min((int)nums1.size()-x,k/2); int c2=min((int)nums2.size()-y,k/2); if(nums1[x+c1-1]<=nums2[y+c2-1]) return getkth(nums1,x+c1,nums2,y,k-c1); else return getkth(nums1,x,nums2,y+c2,k-c2); } double findMedianSortedArrays(vector<int>& nums1,vector<int>& nums2) { int len=nums1.size()+nums2.size(); if(len%2) return getkth(nums1,0,nums2,0,(len+1)/2); else return (getkth(nums1,0,nums2,0,len/2)+getkth(nums1,0,nums2,0,len/2+1))/2.0; } };
这道题目，最令人震惊的是……
我新开一个vector把nums1和nums2的元素都扔进去然后sort了一下，$O(1)$ 输出中位数，明明 $O((m+n) log(m+n))$ 的时间复杂度，居然和 $O(log(m+n))$ 跑的一样快，都是52ms……
感觉自己搞了假的时间复杂度……
所以我开始怀疑，是不是LeetCode用了很水数据，实际上大部分时间是在其他什么地方耗费的，果然，关闭IO同步之后可以 16ms 内跑完：
static const auto io_sync_off = []() { // turn off sync std::ios::sync_with_stdio(false); // untie in/out streams std::cin.tie(nullptr); return nullptr; }(); class Solution { public: inline int getkth(const vector<int>& nums1,int x,const vector<int>& nums2,int y,int k) { if(x>=nums1.size()) return nums2[y+k-1]; //A数组为空 if(y>=nums2.size()) return nums1[x+k-1]; //B数组为空 if(k==1) return min(nums1[x],nums2[y]); int c1=min((int)nums1.size()-x,k/2); int c2=min((int)nums2.size()-y,k/2); if(nums1[x+c1-1]<=nums2[y+c2-1]) return getkth(nums1,x+c1,nums2,y,k-c1); else return getkth(nums1,x,nums2,y+c2,k-c2); } double findMedianSortedArrays(vector<int>& nums1,vector<int>& nums2) { int len=nums1.size()+nums2.size(); if(len%2) return getkth(nums1,0,nums2,0,(len+1)/2); else return (getkth(nums1,0,nums2,0,len/2)+getkth(nums1,0,nums2,0,len/2+1))/2.0; } };
我还同样把上面 $O((m+n) log(m+n))$ 的那个算法关了IO同步试了一下，耗时 32ms……这个 16ms 的差距，应该即使优化复杂度的结果了吧，还算有个安慰。