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

题意

解题思路:

• 满足：l1 < r2 && l2 < r1 表示切割正确

如图所示：

图示:

PHP 代码实现

class Solution {
    function findMedianSortedArrays($nums1, $nums2) {
        //选择一个长度最短的来分割，越少的数分割的次数也会越少
        if (count($nums1) > count($nums2)) {
            return $this->findMedianSortedArrays($nums2, $nums1);
        }
        if (count($nums1) == 0) {
            return floor($nums2[(count($nums2) -1) / 2] + $nums2[count($nums2) / 2]) / 2;
        }
        $len = count($nums1) + count($nums2);
        $cut1 = $cut2 = $cutL = 0;
        $cutR = count($nums1);
        while ($cut1 <= count($nums1)) {
            //满足：l1 < r2 l2 < r1表示切割正确
            $cut1 = floor(($cutR - $cutL) / 2) + $cutL;
            $cut2 = floor($len / 2) - $cut1;
            //cut1 == 0：最左边界
            //l1 = $nums1[$cut1 - 1] => [1, 2] => 1
            //l2 = $nums2[$cut2 - 1] => [3, 4] => 3
            $l1 = ($cut1 == 0) ? PHP_INT_MIN : $nums1[$cut1 - 1];
            $l2 = ($cut2 == 0) ? PHP_INT_MIN : $nums2[$cut2 - 1];
            $r1 = ($cut1 == count($nums1)) ? PHP_INT_MAX : $nums1[$cut1];
            $r2 = ($cut2 == count($nums2)) ? PHP_INT_MAX : $nums2[$cut2];
            //保证l1 < r2
            if ($l1 > $r2) {
                $cutR = $cut1 -1;
            } else if ($l2 > $r1) {//说明找的太小，分割往右移动，因为右边值大于左边值
                $cutL = $cut1 + 1;
            } else {
                // 切完之后判断奇偶数
                // 如果是偶数
                if ($len % 2 == 0) {
                    $l1 = $l1 > $l2 ? $l1 : $l2;
                    $r1 = $r1 < $r2 ? $r1 : $r2;
                    return ($l1 + $r1) / 2;
                }
                //L: 1，3  R:2 如果是奇数，那就是(r1+r2)/2 = (3+2) / 2 = 2.5
                return min($r1, $r2);
            }
        }
    }
    function findMedianSortedArrays1($nums1, $nums2) {
        $arr = array_merge($nums1, $nums2);
        sort($arr);
        $num = count($arr);
        if ($num % 2) return $arr[$num/2];
        //1234 = (2 + 3) / 2
        return round(($arr[$num / 2 - 1] + $arr[$num / 2]) / 2, 10);
    }
}