本文主要是介绍寻找两个正序数组的中位数【php版】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
<?php
class Solution {
/**
* @param Integer[] $nums1
* @param Integer[] $nums2
* @return Float
*/
function findMedianSortedArrays($nums1, $nums2) {
$l1 = count($nums1);
$l2 = count($nums2);
$l = $l1 + $l2;
if ($l % 2 == 1) {
$ans = $this->getKthElm($nums1, $nums2, intdiv($l+1, 2));
} else {
$ansL = $this->getKthElm($nums1, $nums2, intdiv($l, 2));
$ansR = $this->getKthElm($nums1, $nums2, intdiv($l, 2) + 1);
$ans = ($ansL + $ansR) / 2.0;
}
return $ans;
}
/**
* 获取两个数组中,排第k位的元素,使用二分法
* @param $nums1
* @param $nums2
* @param $k
*/
function getKthElm($nums1, $nums2, $k) {
$idx1 = 0;
$idx2 = 0;
$l1 = count($nums1);
$l2 = count($nums2);
while (true) {
// 边界情况
if ($idx1 == $l1) {
return $nums2[$idx2 + $k -1];
}
if ($idx2 == $l2) {
return $nums1[$idx1 + $k - 1];
}
if ($k == 1) {
return min($nums1[$idx1], $nums2[$idx2]);
}
// 正常情况
$half = intdiv($k, 2);
$newIdx1 = min($idx1+$half, $l1) - 1;
$newIdx2 = min($idx2+$half, $l2) - 1;
if($nums1[$newIdx1] <= $nums2[$newIdx2]) {
$k = $k - ($newIdx1 - $idx1 + 1);
$idx1 = $newIdx1 + 1;
} else {
$k = $k - ($newIdx2 - $idx2 + 1);
$idx2 = $newIdx2 + 1;
}
}
}
}
这篇关于寻找两个正序数组的中位数【php版】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!