点击蓝色“五分钟学算法”关注我哟
加个“星标”，天天中午 12:15 ，一起学算法
这道题目很有意思！
忽略时间复杂度的要求的话，so easy ！加上了时间复杂度的要求，so hard！
而很多小伙伴一开始没有注意时间复杂度的要求，还很纳闷：这个难度是困难吗？怎么感觉比简单难度的的还简单啊。
题目来源于 LeetCode 上第 4 号问题：寻找两个有序数组的中位数。题目难度为 Hard，目前通过率为 35.6% 。
题目描述
给定两个大小为 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
题目解析
题目说的是给两个排好序的数组，让你求出这两个数组中所有元素按从小到大排列，排在中间的元素，时间复杂度也是有要求的，O(log(m + n))，m 和 n 分别是这两个数组的长度。
这里提到了时间复杂度为 O(log(m+n)) ，很容易想到的就是二分查找，所以现在要做的就是在两个排序数组中进行二分查找。
具体思路如下，将问题 转化为在两个数组中找第 K 个小的数 。
求中位数，其实就是求第 k 小数的一种特殊情况。
首先在两个数组中分别找出第 k/2 大的数，再比较这两个第 k/2 大的数，这里假设两个数组为 A ，B。
那么比较结果会有下面几种情况：
-
A[k/2] = B[k/2],那么第 k 大的数就是 A[k/2]
-
A[k/2] > B[k/2],那么第 k 大的数肯定在 A[0:k/2+1] 和 B[k/2:] 中，这样就将原来的所有数的总和减少到一半了，再在这个范围里面找第 k/2 大的数即可，这样也达到了二分查找的区别了。
-
A[k/2] < B[k/2]，那么第 k 大的数肯定在 B[0:k/2+1]和 A[k/2:] 中，同理在这个范围找第 k/2 大的数就可以了。
举个例子：
A = [1,3,4,7]
B = [1,2,3,4,5,6,7,8,9,10]
这两个数组总共 14 个数字，是偶数，因此要找出它们的第 15 / 2 = 7 小的数字与第 16 / 2 = 8 小的数字 。
下面以找出第 7 小的数字为例进行说明。
k = 7
k / 2 = 3
分别找出它们的第 k/2 大的数为 4 与 3 。（注意的是如果 k 是奇数，则向下取整）
根据这两个数将 A、B 数组划分为两部分。
然后对比这两个数，上边数组中的 4 和下边数组中的 3，如果哪个小，就表明该数组的前 k/2 个数字都不是第 k 小数字，可以舍弃。
舍弃掉的那三个数字肯定是在 最前面 的数字，因此一开始是要查找第 7 小的数字，现在变成了要查找第 7 – 3 = 4 小的数字。
同样的进行取两个数组的 k/2 数字进行区域划分与比较。
舍弃掉 A 数组的前部分之后，两个数组又发生了变化。
现在变成了去查找第 4 – 2 = 2 小的数字了。
此时出现了一个 特殊情况 ：A 数组的 分割元素 与 B数组的 分割元素 相等，都为 4。
这种情况随意舍弃一个就行！代码编写的时候注意边界判断即可。
舍弃之后，问题简单了：查找两个数组中最小的那个数字。
只需要比较两个数组的开头数字就行了。（别忘记，这两个数组都是递增有序的）
所以第 7 小的数字是 4 。
同样的操作，可以查找出第 8 小的数字是 5。
所以，A 数组和 B 数组的中位数是 （4 + 5）÷ 2 = 4.5。
如果你对上面的图片描述还是有点疑惑的话，强烈建议将下面的动画完整的看完。
动画描述
代码实现
//@author:windliang
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int left = (n + m + 1) / 2;
int right = (n + m + 2) / 2;
//一个小技巧：将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
}
private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
//让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
if (len1 == 0) return nums2[start2 + k - 1];
if (k == 1) return Math.min(nums1[start1], nums2[start2]);
int i = start1 + Math.min(len1, k / 2) - 1;
int j = start2 + Math.min(len2, k / 2) - 1;
if (nums1[i] > nums2[j]) {
return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
}
else {
return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}
}
复杂度分析
时间复杂度：每进行一次循环，减少 k/2 个元素，所以时间复杂度是 O(log(k)，而 k = (m+n) / 2，所以最终的复杂也就是 O(log(m+n）。
空间复杂度：虽然用到了递归，但是可以看到这个递归属于尾递归，所以编译器不需要不停地堆栈，所以空间复杂度为 O(1)。
References
详细通俗的思路分析，多解法
: https://leetcode.wang/leetCode-4-Median-of-Two-Sorted-Arrays.html
本文相关阅读推荐：
GitHub 标星 3w+，很全面的算法和数据结构知识
