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

sPeng 发布于2019-07-01 12:50 / 2350人阅读

摘要：二二分法求解根据上面对中位数的解释，以及对于题目中给出的有序数组，。可以想到，最后肯定是的一部分在中位数的左边，一部分数在中位数的右边，同理。

4. Find Median Sorted Arrays

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;
            }
        }        
    }
    }

总结

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

GPU云服务器云服务器最难的算法题字符串转换为多位数的算法最短寻找时间优先和电梯调度算法 php寻找图片

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/31581.html

JS算法题之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一个字符，判断正负符号，若是英文直接返回，若数字则不取。回文数题目描述判断一个整数是否是回文数。回文数是指正序从左向右和倒序从右向左读都是一样的整数。 JS算法题之leetcode(1~10) 前言一直以来，前端开发的知识储备在数据结构以及算法层面是有所暂缺的，可能归根于我们的前端开发的业务性质，但是我认为任何的编程岗位都离不开数据结构以及算法。因此，我作为...

SoapEye 2019-08-26 10:44 评论0 收藏0
❤️思维导图整理大厂面试高频数组10: 3种方法彻底解决中位数问题, 力扣4❤️

此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...

XanaHopper 2021-09-10 10:51 评论0 收藏0
LeetCode4.寻找两个有序数组的中位数 JavaScript

摘要：寻找两个有序数组的中位数给定两个大小为和的有序数组和。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为。你可以假设和不会同时为空。示例则中位数是示例则中位数是答案参考排序中位数 LeetCode4.寻找两个有序数组的中位数 JavaScript 给定两个大小为m和n的有序数组nums1和nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m +...

habren 2019-08-23 14:46 评论0 收藏0
前端 100 问：能搞懂80%的请把简历给我

摘要：解析第题第题为什么的和的中不能做异步操作解析第题第题京东下面代码中在什么情况下会打印解析第题第题介绍下及其应用。尽量减少操作次数。解析第题第题京东快手周一算法题之两数之和给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。引言半年时间，几千人参与，精选大厂前端面试高频 100 题，这就是「壹题」。在 2019 年 1 月 21 日这天，「壹题」项目正式开始，在这之后每个工...

Scott 2019-08-23 18:35 评论0 收藏0
LeetCode 攻略 - 2019 年 8 月上半月汇总（109 题攻略）

摘要：每天会折腾一道及以上题目，并将其解题思路记录成文章，发布到和微信公众号上。三汇总返回目录在月日月日这半个月中，做了汇总了数组知识点。或者拉到本文最下面，添加的微信等会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。 LeetCode 汇总 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

tracy 2019-08-26 10:49 评论0 收藏0