寻找两个正序数组的中位数

首先，以这个问题为例，Leetcode 的问题描述让你使用 log 级别的算法，但是你使用一个 O(n) 的算法能通过测试，是很正常的。尤其是 Leetcode 题号比较靠前的问题，经常会出现这种情况：即实际时间卡得不严。因为判题系统不会分析你的代码的时间复杂度，只要在规定时间以内，给出正确的结果，就可以。

实际上，对于这个问题，O(nlogn) 的算法应该也可以通过。比如你可以试一下，把两个数组的所有元素都先归入一个数组，然后直接对这个数组排序，然后取 median，应该也是可以通过的。

也正是因为如此，自动判题不能完全取代面试的过程。因为面试官能分析你的代码的实际复杂度。

==========

具体到 logn 级别的算法，其实我觉得 Leetcode 的官方题解讲得挺清楚的：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/

但因为这个问题处理两个数组，还要分若干情况讨论，每种情况都有若干边界，屡清楚本来就是不容易的。我的建议是，你使用一个具体的例子，比如一个数组有 4 个元素，另一个数组有 5 个元素，把具体的数字带进这个题解里的所有这些公式中，去具体看题解的每一步到底在说什么，在证明什么，对应在你的实际例子里，是什么意思。

对于其他题解的理解，也是如此。

依然是，并不是所有的问题都能一句话就能解释清楚，一下子就能明白的。如果是那样的话，算法问题就太容易了。如果你真想攻克这个问题，必须能踏下心来，找一个下午，准备两张白纸，好好模拟一遍题解的思路和代码的思路。这是学习算法的重要方式，进步也就在这个过程中。

==========

不过对于 Leetcode 官方题解，我觉得确实有一种更简单的理解方式它没有提及。

这个方式其实和使用快速排序解决 selectK 问题的思路是一致的。所以，要想理解下面的解法，你首先要充分理解这个课程中介绍的基于快排的 selectK 的算法。具体可以参考这一周课程第二章的 9, 10 小节：https://class.imooc.com/course/1582

首先，这个问题可以转换为 selectK 的问题。（K 为中位数所在的索引，或者在数组长度为偶数时，中间两个元素的索引。）

基于快排的 selectK 算法，每次通过对标定点 pivot 位置和 K 的比较，可以直接扔掉一部分元素。这个问题则是在两个有序数组中，可以采取同样的思路。

即每次看当前处理的两个数组区间的两个中间元素。

如果我们要找的 k，比现在剩下的所有数据的一半还要大，那么小的那个中间元素的左边的元素都可以扔掉；

否则（k < 剩下的所有数据的一半），大的那个中间元素的右边的元素都可以扔掉；

可以结合如下代码在理解一下，仔细想想为什么？

​

代码如下（Java）：

public class Solution {
    
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
        int len = nums1.length + nums2.length;
        
        int a = select(nums1, 0, nums1.length - 1,
                       nums2, 0, nums2.length - 1, len / 2);
        if(len % 2 == 1) return a;
        
        int b = select(nums1, 0, nums1.length - 1,
                       nums2, 0, nums2.length - 1, len / 2 - 1);
        return (a + b) / 2.0;
    }
    
    // 在 nums1[l1...r1] 和 nums2[l2...r2] 的范围里寻找第 k 个元素（从 0 计）
    private int select(int[] nums1, int l1, int r1,
                       int[] nums2, int l2, int r2, int k){
        
        // 如果某一个数组为空，直接取另一个数组区间的第 k 个元素
        if(l1 > r1) return nums2[l2 + k];
        if(l2 > r2) return nums1[l1 + k];
        
        int len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;
        int mid1 = len1 / 2, mid2 = len2 / 2;
        int e1 = nums1[l1 + mid1], e2 = nums2[l2 + mid2];
        
        // k 比两个数组一半的元素还要大
        if(mid1 + mid2 < k){
          
            if(e1 > e2)
                // nums1 中间的元素大于 nums2 中间的元素
                // 则 nums2 中间左边的元素都可以扔掉
                // 注意维护 k，其实和基于快排的 selectK 是一致的
                return select(nums1, l1, r1, nums2, l2 + mid2 + 1, r2, k - mid2 - 1);
            else
                // nums2 中间的元素大于 nums1 中间的元素
                // 则 nums1 中间左边的元素都可以扔掉
                // 注意维护 k，其实和基于快排的 selectK 是一致的
                return select(nums1, l1 + mid1 + 1, r1, nums2, l2, r2, k - mid1 - 1);
        }
        else{
            // k 比两个数组一半的元素还要小
            if(e1 > e2)
                // nums1 中间的元素大于 nums2 中间的元素
                // 则 nums1 中间右边的元素都可以扔掉
                // 此时 k 不变，想想为什么？其实和基于快排的 selectK 是一致的
                return select(nums1, l1, l1 + mid1 - 1, nums2, l2, r2, k);
            else
                // nums2 中间的元素大于 nums1 中间的元素
                // 则 nums2 中间右边的元素都可以扔掉
                // 此时 k 不变，想想为什么？其实和基于快排的 selectK 是一致的
                return select(nums1, l1, r1, nums2, l2, l2 + mid2 - 1, k);
        }
    }
}

这个解法我认为已经非常容易理解了。如果你已经学习了基于快排的 selectK 算法，你会发现代码结构近乎是一样的，只不过现在我们要处理两个数组而已。

但其实在具体实现的时候，还是有很多边界问题需要处理的。如果你有兴趣，可以在理解这个思路的基础上，尝试自己实现一下。在实现过程中遇到问题，再回头仔细比较一下和我提供的这个代码的差距。

继续加油！：）