这道算法题太简单？你忽略了时间复杂度的要求！

小咪咪 2021-11-05 16:12 215阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15 ，一起学算法

![640][]

这道题目很有意思！

忽略时间复杂度的要求的话，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.0

**示例 2:**

nums1 = [1, 2]nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5
    
    则中位数是 (2 + 3)/2 = 2.5

### 题目解析 ###

题目说的是给两个排好序的数组，让你求出这两个数组中所有元素按从小到大排列，排在中间的元素，时间复杂度也是有要求的，O(log(m + n))，m 和 n 分别是这两个数组的长度。

这里提到了时间复杂度为 O(log(m+n)) ，很容易想到的就是**二分查找**，所以**现在要做的就是在两个排序数组中进行二分查找**。

具体思路如下，将问题 **转化为在两个数组中找第 K 个小的数** 。

求中位数，其实就是求第 `k` 小数的一种特殊情况。

首先在两个数组中分别找出第 k/2 大的数，再比较这两个第 k/2 大的数，这里假设两个数组为 A ，B。

那么比较结果会有下面几种情况：

举个例子：

A = [1,3,4,7]B = [1,2,3,4,5,6,7,8,9,10]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 数组划分为两部分。

![640?wx\_fmt=png][640_wx_fmt_png]

然后对比这两个数，上边数组中的 4 和下边数组中的 3，如果哪个小，就表明该数组的前 k/2 个数字都不是第 k 小数字，可以舍弃。

![640?wx\_fmt=gif][640_wx_fmt_gif]

舍弃掉的那三个数字肯定是在 **最前面** 的数字，因此一开始是要查找第 **7** 小的数字，现在变成了要查找第 **7 - 3 = 4** 小的数字。

![640?wx\_fmt=png][640_wx_fmt_png 1]

同样的进行取两个数组的 k/2 数字进行区域划分与比较。

![640?wx\_fmt=gif][640_wx_fmt_gif 1]

舍弃掉 A 数组的前部分之后，两个数组又发生了变化。

![640?wx\_fmt=png][640_wx_fmt_png 2]

现在变成了去查找第 **4 - 2 = 2** 小的数字了。

此时出现了一个 **特殊情况** ：A 数组的 **分割元素** 与 B数组的 **分割元素** 相等，都为 4。

这种情况随意舍弃一个就行！代码编写的时候注意边界判断即可。

舍弃之后，问题简单了：查找两个数组中最小的那个数字。

只需要比较两个数组的开头数字就行了。（别忘记，这两个数组都是递增有序的）

![640?wx\_fmt=png][640_wx_fmt_png 3]

所以第 7 小的数字是 4 。

同样的操作，可以查找出第 8 小的数字是 5。

![640?wx\_fmt=png][640_wx_fmt_png 4]

所以，A 数组和 B 数组的中位数是 **（4 + 5）÷ 2 = 4.5**。

![640?wx\_fmt=png][640_wx_fmt_png 5]

如果你对上面的图片描述还是有点疑惑的话，强烈建议将下面的动画完整的看完。

### 动画描述 ###

### 代码实现 ###

//@author:windliangpublic 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));        }    }
    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*

--------------------

**本文相关阅读推荐：**

[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[一道腾讯面试题：厉害了我的杯][Link 2]

[十大经典排序算法动画与解析，看我就够了][Link 3]

[这或许是东半球分析十大排序算法最好的一篇文章][Link 4]

[面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

[看《长安十二时辰》可以了解哪些算法知识][Link 5]

GitHub 标星 3w+，很全面的算法和数据结构知识

![640?wx\_fmt=png][640_wx_fmt_png 6]

[640]: /images/20211104/29333ee71ef0400fa5a0f7691d73e625.png
[640_wx_fmt_png]: /images/20211104/58e5187a420145088aad7a4ae0d458be.png
[640_wx_fmt_gif]: /images/20211104/c58b15f92d644a9b8ca54ffd24e199b7.png
[640_wx_fmt_png 1]: /images/20211104/32dd4c9f4b084effa2556bda6a9129de.png
[640_wx_fmt_gif 1]: /images/20211104/43c9a262d8f54e2db73a884f9ad452bb.png
[640_wx_fmt_png 2]: /images/20211104/17a856652c254321904f3fbf1b8d3173.png
[640_wx_fmt_png 3]: /images/20211104/8e3cd42686f64a00b651fd6cc16db81e.png
[640_wx_fmt_png 4]: /images/20211104/85315bf685fa4f48a471433df2a9dc59.png
[640_wx_fmt_png 5]: /images/20211104/adad6f558e9a48f0be2b84ceb82485a9.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 3]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 4]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485904&idx=1&sn=0eae783ce1b7c0383f41d76a269f511e&chksm=fa0e6651cd79ef47d31a0dba6909873974a964e81654cf702e3868da51fa9a695e7b9a383c1a&scene=21#wechat_redirect
[640_wx_fmt_png 6]: /images/20211104/8d7ad8fe48b5464cb2691e2f3b183d69.png