题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。复杂度O(log (m+n))。

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

PHP

<?php
// 1,2,2,2,3,4,5,6,7,8,9 共11位
//$a = [2,2,3,4,5,6,7];
//$b = [1,2,8,9];

// 1,2,2,3,4,5,6,7,8,9 共10位
$a = [2,3,4,5,6,7];
$b = [1,2,8,9];

$count = count($a) + count($b);

if ($count%2 != 1) {
    $cursor = $count/2;
    $x = getMin($a,$b,$cursor);
    $y = getMin($a,$b,$cursor+1);
    print_r(($x+$y)/2);
}else{
    // 如果是奇数 找出第 $cursor 小的数字 就是中位数
    $cursor = ($count+1)/2;
    $x = getMin($a,$b,$cursor);
    print_r($x);
}

function getMin($nums1,$nums2,$cursor){
    [$m, $n] = [count($nums1), count($nums2)];
    [$index1, $index2] = [0, 0];
    while( 1 ){
        # 特殊情况
        if ($index1 == $m)
            return $nums2[$index2 + $cursor - 1];
        if ($index2 == $n)
            return $nums1[$index1 + $cursor - 1];
        if ($cursor == 1)
            return min($nums1[$index1], $nums2[$index2]);
        # 正常情况
        $newIndex1 = min($index1 + floor($cursor/2) - 1, $m - 1);
        $newIndex2 = min($index2 + floor($cursor/2) - 1, $n - 1);
        [$pivot1, $pivot2] = [$nums1[$newIndex1], $nums2[$newIndex2]];
        if ($pivot1 <= $pivot2){
            $cursor = $cursor - $newIndex1 + $index1 - 1;
            $index1 = $newIndex1 + 1;
        } else {
            $cursor = $cursor - $newIndex2 + $index2 - 1;
            $index2 = $newIndex2 + 1;
        }
    }
}