用 PHP 在力扣刷算法 [寻找两个正序数组的中位数]{有空就更}

666666 的个人博客 / 74 / 0 / 创建于 3年前 / 更新于 3年前

题目：题目：

给定两个大小为 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

解析：

1，看到这个题的瞬间，先不考虑题目中的时间和空间的复杂度，我用PHP的 array_merge()一下这两个数组，然后在sort() 一下，在 count() 一下，计算出中位数的下标，就得到了。当然，这肯定不符合题意的。又回到题目，我要求时间和空间复查度都要要小于log级别，看到这三个单词，我想到了二分天下中，这就是标准的时间空间的级别，那么，现在的问题是怎么二分？

首先：1，两个有序数组找中位数，必然中位数在其中一个有序数组中，并且在这个数组中存在这样的关系：数组中位数的左边的所有值肯定都小于右边的所有值。

其次：2，既然这个中位数是这两个有序数组的中位数，那如果合并两个数组后，比中位数小的或等于元素个数加比中位数大的元素个数必然等于两个数组的总数，反过来说，不合并也是存在这个等式的

再其次：3，根据第一个分析，不管两个有序数组怎么样，比中位数小的在左边，其中一个数组的比中位数小的所有元素中的最大元素必定比另一个有序数组比中位数大的元素小，反过来也必须成立。

最后：4，我们对其中一个数组进行二分，那必然满足 2 的规则。

注意：计算中位数时，要判断两个数组的总长度，奇数是刚好中间的元素，偶数是中间两个元素的和处以2

## 分析那么多，不如看代码：

function findMedianSortedArrays($nums1, $nums2) {
        // 统计两个数组长度
        $len1 = count($nums1);
        $len2 = count($nums2);
        // 既然二分任何一个有序数组都可以，那么就选 个数小的那个进行二分, 如果传参的第一个数组大于第二个，递归一下
        if ($len1 > $len2) {
            $this->findMedianSortedArrays($nums2, $nums1);
        }
        // 再判断 $nums1 数组长度是否为 0 ，如果是零，则就是查找 $nums2 的中位数，那么就简单了三
        if ($len1 == 0) {
            // 一个有序数组 不管是奇数还是偶数，这个写法都能准确找到中位数，这个就不解释了，可以自己试试
            return ($nums2[floor($len2 / 2)] + $nums2[floor(($len2 - 1) / 2)]) / 2;
        }

        // 开始分割查找:

        // 统计一下两个数组的总长度
        $len = $len1 + $len2;

        //  对 $nums1 进行切得 下标
        $slice1 = 0;
        // 根据解析 中第二条能推导出 $nums2 得切点，但是还是要预存一下
        $slice2 = 0;
        // $nums1 的切割区间 左 和 右 
        $sliceL = 0;
        $sliceR = $len1;
        // 接下来就是在循环找找出 中位数了
        // 只要切点 不大于 长度，那么就是成立的
        while ($slice1 <= $len1) {
            // 刚进来时 先对 小的数组进行二分   ($sliceL + $sliceR)/2 和 ($sliceR - $sliceL) / 2 + $sliceL 在数学上是一样的，但是第二种可以防止内存溢出 
            $slice1  = floor($sliceR - $sliceL) / 2 + $sliceL;
            // 得到小数组的切点，那么大数组的二分切点也知道了，因为满足上面分析的第二条
            // 简单证明一下，第一个切点等式：2*$slice1 = $sliceR - $sliceL 
            // $len = $len1 + $len2 
            // 根据二分 $len2 = 2 * $slice2
            // 替换一下上面的等式 $len = 2 * $slice1 + 2 * $slice2
            // 得到下面的等式
            $slice2 = floor($len/2) - $slice1;
            // 计算 $nums1 被分过后小的半段的最大元素，比如数组 [1, 3, 4, 6, 8, 13] 中分后为 [[1, 3, 4] 和   [6, 8, 13] 
            // 根据不断的移动切点 有可能切点在 开始位置 ，当为开始位置时，要找一个肯定小的标记，这里用 PHP 的系统常量，否则就是切点的前一个
            $l1 = ($slice1 == 0) ? PHP_INT_MIN :$nums1[$slice1 - 1];
            $l2 = ($slice2 == 0) ? PHP_INT_MIN :$nums2[$slice2 - 1];
             // 同理，计算数组大的半段的最小元素 也存在一个当切点是数组长度时 
            $r1 = ($slice1 == $len1) ? PHP_INT_MAX : $nums1[$slice1];
            $r2 = ($slice2 == $len2) ? PHP_INT_MAX : $nums2[$slice2];
            // 根据解析 第三条 其中一个数组的比中位数小的所有元素中的最大元素 必定比另一个有序数组比中位数大的元素小 
            if ($l1 > $r2) {
                // 如果大了 则不是中位数 要向左移动切点，找前一个值，本体的二分就体现在这里，大了，则后面的全部值都大了，直接不进入计算了
                $cutR = $slice1 - 1;
            // 同理 $nums2 切割后 所有小的元素中的最大值也 必须小于 $nums1 切割后 所有大元素的最小值。
            } elseif ($l2 > $r1) {
                // 直接抛弃切点的前半段，在二分
                $cutL = $slice1 + 1;
            // 当上面的 两个都满足，则找到了本题的中位数了，
            } else {
                // 偶数时，中位数时 小的所有元素的最大值和大的所有元素的最小值相加除2
                if ($len % 2 ==0) {
                    $l1 = $l1 > $l2 ? $l1 : $l2;
                    $r1 = $r1 < $r2 ? $r1 : $r2;
                    return ($l1 + $r1) / 2;
                }
                // 奇数时，所有大元素的最小值
                return min($r1, $r2);
            }
        }