php算法题:寻找有序数组的中位数

栏目: PHP · 发布时间: 5年前

内容简介: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;
        }
    }        
}
}

讲解问题的能力还有待进一步提高。如果有问题欢迎私聊。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

人人都在说谎

人人都在说谎

赛思·斯蒂芬斯--达维多维茨 / 胡晓姣、张晨、左润男 / 中信出版集团 / 2018-11 / 58

有多少人买了书真正看完了? 你朋友的酒量有他说的那么大吗? 父母是否暗自喜欢男孩儿多于女孩儿? 电影里暴力镜头增多会导致犯罪率升高吗? 种族歧视在现如今的美国还严重吗? 特朗普的胜利有征兆吗,什么促成他赢得了大选? …… 你知道问题的答案吗,直觉会怎样告诉你? 作者赛思·斯蒂芬斯--达维多维茨是一位前谷歌数据科学家和专栏作家。他的研究发现,世界充满了......一起来看看 《人人都在说谎》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

MD5 加密
MD5 加密

MD5 加密工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具