拿起算法的钢笔: 找出两个有序数组的中位数

summerpxy 发布于2019-08-26 10:28 / 919人阅读

摘要：给定两个大小为和的有序数组和题目请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为。一般我们的二分搜索是一个有序数组，查找元素，每一次查找，把搜索范围缩减一半。

给定两个大小为 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

分析： 常规做法，是 O(m+n)

两个有序数组，合并成一个有序数组，取中位数，
思路很清晰

这里只要取中位数，只要保证，这个数字左边的元素个数（数组一左边 i 个+数组二左边 j 个）与右边的元素个数相等，这个数字左边的元素都小于右边的元素，

就可以认为，这个数字是我们想要的

先分片, 保证找到的中位数，这个数字左边的元素个数（数组一左边 i 个+数组二左边 j 个）与右边的元素个数相等

因为是中间位置的数字，
如果第一个数组 nums1 取 i 个，（ 0 <= i <= m ）,
那么第二个数组 nums2 里面取 j 个, （ 0 <= j <= n ）,

i 与 j 满足一定的关系 i + j = ( m + n )/2 , 或者 i + j = ( m + n + 1)/2 , 因为 m + n 可能是奇数，也可能是偶数。
那么 j = ( m + n + 1 ) / 2 - i

再取值，这个数字左边的元素都小于右边的元素

i 和 j 把两个数组，各分成两片，出现了四个关键的数字，

数组一左边最大，num1LeftMax

数组一右边最小，num1RightMin

数组二左边最大，num2LeftMax

数组二右边最小，num2RightMin

如果 num1LeftMax <= num2RightMin, num2LeftMax <= num1RightMin, 就找到我们想要的中位数了，因为 num1 是有序数组，num1LeftMax 当然小于 num1RightMin，同样的 num2LeftMax < num2RightMin

O(m), 因为这就是二分搜索，搜索条件不是很直接

为什么是 O(m), 因为这就是二分搜索。

一般我们的二分搜索是一个有序数组，查找元素，每一次查找，把搜索范围缩减一半。通过移动上边界和下边界

就是比较条件相对简单，直接比元素大小

这道题其他与基础的二分查找一致，比较条件有些变化

如果 num1LeftMax > num2RightMin, 数字一左边的大了，就是 i 大了，就要移动右边界，就是右边界变小

（左边界只能右移，只能变大。右边界只能左移，只能变小）

其他情况，类似处理

拿起算法的钢笔，跑一遍

示例 3:

nums1 = [ 1, 3，8，9，15 ]nums2 = [ 7， 11， 18， 19， 21，25 ]

中位数是 11

左边有 5 个元素， m = 5,

右边有 6 个， n = 6

数组一右边最小，num1RightMin < 数组二左边最大，num2LeftMax
就是 i 小了，左边界右移， low = 3

现在满足要求了，m + n 是奇数，左边多一个，选数组一左边最大和数组二左边最大中较大的，就是 11

拿起算法的钢笔，再跑一遍，为了印象深刻

示例 4:

nums1 = [ 23, 26，31，35 ]nums2 = [ 3， 5， 7， 9， 11，16 ]

中位数是 13.5， 11 和 16 的平均值

左边有 4 个元素， m = 4,

右边有 6 个， n = 6

数组一左边最大，num1LeftMax > 数组二右边最小，num2RightMin
就是 i 大了，右边界左移, high = 1

左边一个元素都不要，默认数组一左边最大为负无穷，num1LeftMax = Number.MIN_SAFE_INTEGER,

现在满足要求了，m + n 是偶数，找出中间两个 11 与 16，求平均值为 13.5

PS: 个人看，看书和看算法动画，不错，就是少了一点参与感。
拿起钢笔，写写画画，需要保证结果一致嘛，我感觉，理解的好一些

代码如下：

选短的数组处理，处理快，还保证了 j 一定大于 0 （因为 n > m），避免了一些逻辑处理。

里面处理了一些边界条件， i = 0, 第一个数组左边一个元素都不要，i = m, 第一个数组右边一个元素都不要

m + n 的值是奇数，这个好处理一点，只需要找出一个元素

m + n 的值是偶数，需要找出两个元素

var findMedianSortedArrays = function (nums1, nums2) {
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1]
    }
    const arr1Length = nums1.length, arr2Length = nums2.length;
    let low = 0, high = arr1Length;
    const halfLen = Math.floor((arr1Length + arr2Length + 1) / 2);

    while (low <= high) {
        let i = Math.floor((low + high) / 2); 
        let j = halfLen - i;
        let num1LeftMax = i == 0 ? Number.MIN_SAFE_INTEGER : nums1[i - 1]
        let num1RightMin = i == arr1Length ? Number.MAX_SAFE_INTEGER : nums1[i]
        let num2LeftMax = j == 0 ? Number.MIN_SAFE_INTEGER : nums2[j - 1]
        let num2RightMin = j == arr2Length ? Number.MAX_SAFE_INTEGER : nums2[j]
        if (num1LeftMax <= num2RightMin && num2LeftMax <= num1RightMin) {
            var answer = 0
            if (Math.round((arr1Length + arr2Length) % 2) == 1) {
                answer = Math.max(num1LeftMax, num2LeftMax)
            }
            else {
                // Math.round((arr1Length + arr2Length) % 2) == 0
                let leftMax = Math.max(num1LeftMax, num2LeftMax)
                let rightMin = Math.min(num1RightMin, num2RightMin)
                answer = (leftMax + rightMin) / 2
            }
            return answer
        }
        else if (num1LeftMax > num2RightMin) {
            high = i - 1
        }
        else { // num2LeftMax > num1RightMin
            low = i + 1
        }
    }
    return 0;
};

我还喜欢看视频，有一个 youtube ,链接是 https://www.youtube.com/watch... .

本文可以作为该视频和 Leatcode 官方题解的补充，官方题解: https://leetcode.com/problems...

云服务器 GPU云服务器字符串转换为多位数的算法 linux 找出的数据 cp linux+找出的数据+cp java 集合有序的

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

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

LeetCode4.寻找两个有序数组的中位数 JavaScript

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

habren 2019-08-23 14:46 评论0 收藏0
JS算法题之leetcode(1~10)

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

SoapEye 2019-08-26 10:44 评论0 收藏0
一些前端算法詳解 --- (不定时更新)

摘要：也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因於年提出而得名。前言因為比较随心所欲,所以我不按难度分享算法,所以你们会看到有时候顺序有变化,因為我发表的时候会按照难度修改下位置,尽量让你们看的时候能从简单开始,以后每次更新都加个更新时间好了,让你们知道我进度.新增计时函数直观对比效率并且因為资料比较杂,很多都是我个人理解说法,如果有发...

Baaaan 2019-08-26 10:35 评论0 收藏0
前端 100 问：能搞懂80%的请把简历给我

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

Scott 2019-08-23 18:35 评论0 收藏0