题目链接

4. 寻找两个正序数组的中位数 难度：hard

有点相似TopK问题,只是这里是有有序的，二分找到中位数即可。

解法

1.合并排序

暴力解法，略过不提

2.二分求中位数

将两个数组切割，假如A数组长度为m，切割地位为i，B数组长度为n，切割地位为j，则有：

左半局部的长度等于右半局部，即：i + j = m - i  + n - j  , 也就是 j = ( m + n ) / 2 - i（当 A 数组和 B 数组的总长度是奇数时，j = ( m + n + 1) / 2 - i）因为向下取整，故而j = ( m + n ) / 2 - i和j = ( m + n + 1) / 2 - i后果是统一的此时，只有满足max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））即找到了中位数
复杂度剖析
  • 工夫复杂度：O(min(m,n))，其中 m,n 为两个数组的长度。咱们对长度较短的数组进行二分。
  • 空间复杂度：O(1)。

以下为PHP语言实现~~~~

class Solution {    /**     * @param Integer[] $nums1     * @param Integer[] $nums2     * @return Float     */    function findMedianSortedArrays($nums1, $nums2) {        $a = $nums1;        $b = $nums2;        $m = count($a);        $n = count($b);        if ($m > $n) {            $tmp = $a;            $a = $b;            $b = $tmp;            list($m,$n) = [$n,$m];        }        $mid = (int)(($m+$n+1)/2);        $i_min = 0;        $i_max = $m;        $count = 0;        while ($i_min <= $i_max) {            $i = (int)(($i_min + $i_max)/2);            $j = $mid - $i;            if ($i < $i_max && $b[$j-1] > $a[$i] ) {                $i_min=$i+1;            }elseif ($i > $i_min && $a[$i-1] > $b[$j]) {                $i_max=$i-1;            }else{                if ($i == 0) {                    $max_left = $b[$j-1];                }elseif ($j == 0) {                    $max_left = $a[$i-1];                }else{                    $max_left = $a[$i-1] > $b[$j-1] ?$a[$i-1]:$b[$j-1];                }                if (($m+$n)%2 == 1) {                    return $max_left;                }                if ($i == $m) {                    $min_right = $b[$j];                }elseif ($j == $n) {                    $min_right = $a[$i];                }else{                    $min_right = $a[$i] < $b[$j] ?$a[$i]:$b[$j];                }                $res = ($max_left+$min_right)/2;                return $res;            }        }    }}