内容简介:There are two sorted arrays nums1 and nums2 of size m and n respectively.Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).You may assume nums1 and nums2 cannot be both empty.
4:FindMedianSortedArrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3] nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
一、按时间复杂度O(m+n)解
先来解释一下什么是中位数
如下: [3,4,5] , 那么这组数的中位数就是4 [3,4,5,6] , 那么这组数的中位数就是 (4+5)/2 = 4.5
开始没有注意到时间复杂度,但按照O(m+n)解,也花了我不少时间,可能是很久没有接触算法的缘故。
二、二分法求解
根据上面对中位数的解释,以及对于题目中给出的有序数组nums1[m],nums2[n]。可以想到,最后肯定是nums1的一部分在中位数的左边,一部分数在中位数的右边,nums2同理。
所以咱们可以将nums1和nums2,合并后划分成,左右两个数组。
nums1[0],...,nums1[i-1] | nums1[i] ... nums1[m-1] nums2[0],...,nums2[j-1] | nums2[j] ... nums2[m-1]
也可以看成是下面这种
nums1[0],...,nums1[i-1],nums2[0],...,nums2[j-1] | nums1[i] ... nums1[m-1],nums2[j] ... nums2[m-1]
左右两个数组的总数可能是奇数,也可能是偶数。所以规定,如果是 奇数 ,那么左边比右边多一个,如果是 偶数 ,那么左右两边相等。
这里来说一下i和j的关系
左边数组的个数 t =(int)(m+n+1)/2
j = t - i.
理解清楚了i和j的关系之后,那么接下来就要判断中位数了
抓住数组有序这个条件。
可知如果满足中位数的条件左边最大的数leftMax 小于 右边最小的数rightMin
并且左边数组个数一定是等于右边数组个数,或者是比右边数组个数多1个。
最重要的来了
根据上面一系列的条件,那么现在要做的就是通过二分法选出合适的i,进而得到中位数
还得考虑边界问题,这个在下面代码中给出注释
代码如下:
class Solution{ /** * @param Integer[] $nums1 * @param Integer[] $nums2 * @return Float */ function findMedianSortedArrays($nums1, $nums2) { $m = count($nums1); $n = count($nums2); //如果$m>$n时,后面的$j会可能小于0。也就是上面提到的不等式( t =(int)(m+n+1)/2。j = t - i.) if($m>$n) return $this->findMedianSortedArrays($nums2,$nums1); $t = (int)(($m+$n+1)/2); $i = 0; $j = 0; /** 要理解清楚下面两组max,min的意思 */ $leftMax = 0;//左边数组的最大值 $rightMin = 0;//右边数组的最小值 $iMax = $m;//二分法的右边界 $iMin = 0;//二分法的左边界 while($iMax >= $iMin){ //二分法 $i = (int)(($iMax+$iMin)/2); $j = $t-$i; if ($i>0 && $j<$n && $nums1[$i-1] > $nums2[$j]){//利用数组有序,可以只比较一次 $iMax=$i-1; }elseif ($j>0 && $i<$m && $nums1[$i] < $nums2[$j-1]){//利用数组有序,可以只比较一次 $iMin=$i+1; }else{//二分到最后 最佳位置 if ($i==0){ $leftMax = $nums2[$j-1]; }elseif ($j==0){ $leftMax = $nums1[$i-1]; }else { $leftMax = max($nums2[$j-1],$nums1[$i-1]); } if(($m+$n)%2 == 1){//数组和是奇数 return $leftMax; } //数组和是奇数 if ($i == $m){ $rightMin = $nums2[$j]; }elseif ($j == $n){ $rightMin = $nums1[$i]; }else { $rightMin = min($nums2[$j],$nums1[$i]); } return ($leftMax+$rightMin)/2; } } } }
讲解问题的能力还有待进一步提高。如果有问题欢迎私聊。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- Leetcode-计算两个排序数组的中位数
- 归并排序思想求两个有序数组的中位数
- LeetCode4.寻找两个有序数组的中位数 JavaScript
- 『算法导论』第 9 章:中位数与顺序统计量
- C语言指针数组和数组指针
- 数组 – 如何在Swift中将数组拆分成两半?
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Python高性能编程
【美】 戈雷利克 (Micha Gorelick)、【美】 欧日沃尔德(Ian Ozsvald) / 人民邮电出版社 / 2017-7-1 / 79
本书共有12章,围绕如何进行代码优化和加快实际应用的运行速度进行详细讲解。本书主要包含以下主题:计算机内部结构的背景知识、列表和元组、字典和集合、迭代器和生成器、矩阵和矢量计算、并发、集群和工作队列等。最后,通过一系列真实案例展现了在应用场景中需要注意的问题。 本书适合初级和中级Python程序员、有一定Python语言基础想要得到进阶和提高的读者阅读。一起来看看 《Python高性能编程》 这本书的介绍吧!