题目链接
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;
}
}
}
}