请注意,本文编写于 1715 天前,最后修改于 1542 天前,其中某些信息可能已经过时。
给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。
请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
- nums1 = [1, 3]
- nums2 = [2]
- 则中位数是 2.0
示例 2:
- nums1 = [1, 2]
- nums2 = [3, 4]
-
- 则中位数是 (2 + 3)/2 = 2.5
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays
PHP解法
- class Solution {
-
- /**
- * @param Integer[] $nums1
- * @param Integer[] $nums2
- * @return Float
- */
- function findMedianSortedArrays($nums1, $nums2) {
- $a = array_merge($nums1, $nums2);
- $c = count($a);
- $k = (int)($c / 2);
-
- sort($a);
-
- if ($c % 2 === 0) {
- return ($a[$k] + $a[$k-1]) / 2;
- }
-
- return $a[$k];
- }
- }
-
作者:young-162
链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/zhi-xing-yong-shi-32-ms-zai-suo-you-php-ti-jiao-2/
C语言解法
- #include <stdio.h>
- #include <vector>
- using namespace std;
-
- #define max(a,b) (((a) > (b)) ? (a) : (b))
- #define min(a,b) (((a) < (b)) ? (a) : (b))
-
- class Solution {
- public:
- double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
- int n = nums1.size();
- int m = nums2.size();
-
- if (n > m) //保证数组1一定最短
- {
- return findMedianSortedArrays(nums2, nums1);
- }
-
- // Ci 为第i个数组的割,比如C1为2时表示第1个数组只有2个元素。LMaxi为第i个数组割后的左元素。RMini为第i个数组割后的右元素。
- int LMax1, LMax2, RMin1, RMin2, c1, c2, lo = 0, hi = 2 * n; //我们目前是虚拟加了'#'所以数组1是2*n长度
-
- while (lo <= hi) //二分
- {
- c1 = (lo + hi) / 2; //c1是二分的结果
- c2 = m + n - c1;
-
- LMax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
- RMin1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2];
- LMax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
- RMin2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];
-
- if (LMax1 > RMin2)
- hi = c1 - 1;
- else if (LMax2 > RMin1)
- lo = c1 + 1;
- else
- break;
- }
- return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;
- }
- };
-
-
- int main(int argc, char *argv[])
- {
- vector<int> nums1 = { 2,3, 5 };
- vector<int> nums2 = { 1,4,7, 9 };
-
- Solution solution;
- double ret = solution.findMedianSortedArrays(nums1, nums2);
- return 0;
- }
-
作者:bian-bian-xiong
链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/
全部评论 (暂无评论)
info 还没有任何评论,你来说两句呐!