leetcode-4. 寻找两个有序数组的中位数

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

解题思路一

简单粗暴，先将两个数组合并，两个有序数组的合并也是归并排序中的一部分。然后根据奇数，还是偶数，返回中位数。

<?php

class Solution
{
    /**
     * 4. 寻找两个有序数组的中位数
     * @param array $nums1
     * @param array $nums2
     * @return float|int|mixed
     */
    function findMedianSortedArrays($nums1, $nums2)
    {
        $nums = []; //　合并后的新数组
        $m = count($nums1);
        $n = count($nums2);
        if ($m == 0) {//第一个数组为空
            if ($n % 2 == 0) { // 第二个数组长度为偶数
                return ($nums2[$n / 2] + $nums2[($n / 2) - 1]) / 2;
            } else {
                return $nums2[$n / 2];
            }
        }
        if ($n == 0) {//第二个数组为空
            if ($m % 2 == 0) { // 第一个数组长度为偶数
                return ($nums1[$m / 2] + $nums1[($m / 2) - 1]) / 2;
            } else {
                return $nums1[($m) / 2];
            }
        }

        $count = 0;
        $i = 0;
        $j = 0;
        while ($count != ($m + $n)) {
            if ($i == $m) {
                while ($j != $n) {
                    $nums[$count++] = $nums2[$j++]; //　$nums[$count]=$nums2[$j] $count+1 $j+1

                }
                break;//跳出整个循环

            }
            if ($j == $n) {
                while ($i != $m) {
                    $nums[$count++] = $nums1[$i++];
                }
                break;
            }
            if ($nums1[$i] < $nums2[$j]) {
                $nums[$count++] = $nums1[$i++];
            } else {
                $nums[$count++] = $nums2[$j++];
            }

        }

        if ($count % 2 == 0) { // 数组长度为偶数
            return ($nums[($count / 2) - 1] + $nums[$count / 2]) / 2;
        } else {
            return $nums[$count / 2];
        }

    }

}


$solution = new Solution();
$nums1 = [1, 3, 5, 6];
$nums2 = [2];
echo ($solution->findMedianSortedArrays($nums1, $nums2)) . PHP_EOL;
$nums1 = [1, 3];
$nums2 = [2];
echo ($solution->findMedianSortedArrays($nums1, $nums2)) . PHP_EOL;
$nums1 = [1, 2];
$nums2 = [3, 4];
echo($solution->findMedianSortedArrays($nums1, $nums2)).PHP_EOL;
$nums1 = [];
$nums2 = [1];
echo($solution->findMedianSortedArrays($nums1, $nums2));
结果：
3
2
2.5
1

时间复杂度：遍历全部数组 (m+n)
空间复杂度：开辟了一个数组，保存合并后的两个数组 O(m+n)

解题思路二

上边的解题思路，时间复杂度达不到题目的要求 O(log(m+n)。看到 log，很明显，我们只有用到二分的方法才能达到。我们不妨用另一种思路，题目是求中位数，其实就是求第 k 小数的一种特殊情况，而求第 k 小数有一种算法。

数列是有序的，其实我们可以一半儿一半儿的排除。假设我们要找第 k 小数，我们可以每次循环排除掉 k/2 个数。

为了防止数组长度小于 k/2，所以每次比较 min(k/2，len(数组) 对应的数字，把小的那个对应的数组的数字排除，将两个新数组进入递归，并且 k 要减去排除的数字的个数。递归出口就是当 k=1 或者其中一个数字长度是 0 了。

<?php

class Solution
{
    /**
     * 4. 寻找两个有序数组的中位数
     * @param array $nums1
     * @param array $nums2
     * @return float|int|mixed
     */
    function findMedianSortedArrays($nums1, $nums2)
    {
        $m = count($nums1);
        $n = count($nums2);
        //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
        $left = intval(($m + $n + 1) / 2); //中间最小的两个数之左边数位置
        $right = intval(($m + $n + 2) / 2);//中间最小的两个数之右边数位置
        return ($this->getKth($nums1, 0, $m - 1, $nums2, 0, $n - 1, $left)
                + $this->getKth($nums1, 0, $m - 1, $nums2, 0, $n - 1, $right))
            * 0.5;
    }

    /**
     * 求第ｋ小
     * @param $nums1
     * @param $start1
     * @param $end1
     * @param $nums2
     * @param $start2
     * @param $end2
     * @param $k
     * @return mixed|string
     */
    private function getKth($nums1, $start1, $end1, $nums2, $start2, $end2, $k)
    {
        $len1 = $end1 - $start1 + 1;
        $len2 = $end2 - $start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
        if ($len1 > $len2) {
            return $this->getKth($nums2, $start2, $end2, $nums1, $start1, $end1, $k);
        }
        if ($len1 == 0) {//其中一个数组为空的情况
            return $nums2[$start2 + $k - 1];
        }
        if ($k == 1) {//　求第１小的情况
            return min($nums1[$start1], $nums2[$start2]);
        }
        $i = $start1 + min($len1, intval($k / 2)) - 1;
        $j = $start2 + min($len2, intval($k / 2)) - 1;

        if ($nums1[$i] > $nums2[$j]) {
            return $this->getKth($nums1, $start1, $end1, $nums2, $j + 1, $end2, $k - ($j - $start2 + 1));
        } else {
            return $this->getKth($nums1, $i + 1, $end1, $nums2, $start2, $end2, $k - ($i - $start1 + 1));
        }

    }

}


$solution = new Solution();
$nums1 = [1, 3, 5, 6];
$nums2 = [2];
echo ($solution->findMedianSortedArrays($nums1, $nums2)) . PHP_EOL;
$nums1 = [1, 3];
$nums2 = [2];
echo ($solution->findMedianSortedArrays($nums1, $nums2)) . PHP_EOL;
$nums1 = [1, 2];
$nums2 = [3, 4];
echo ($solution->findMedianSortedArrays($nums1, $nums2)) . PHP_EOL;
$nums1 = [];
$nums2 = [1];
echo($solution->findMedianSortedArrays($nums1, $nums2));
结果：
3
2
2.5
1

时间复杂度：每进行一次循环，我们就减少 k/2 个元素，所以时间复杂度是 O(log(k)，而 k=(m+n)/2，所以最终的复杂也就是 O(log(m+n）。
空间复杂度为 O(1)。