寻找两个正序数组的中位数【php版】
2021/8/2 17:06:16
本文主要是介绍寻找两个正序数组的中位数【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版】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-03-29env: php: no such file or directory
- 2024-03-01php foreach break
- 2024-02-26Exception参数 php-icode9专业技术文章分享
- 2023-12-30PHP文件批量上传-icode9专业技术文章分享
- 2023-12-30thinkphp6 withJoin-icode9专业技术文章分享
- 2023-12-27MagicArray:像php一样,让Go业务代码不再卷!
- 2023-11-18centos7编译安装PHP教程。
- 2023-11-18centos7编译安装phpMyAdmin教程。
- 2023-10-13唱衰这么多年,PHP 仍然还是你大爷!
- 2023-07-25PHP8,性能更好,语法更好,类型安全更完善