leetcode top100挑战, 每天不鸽一道题之寻找两个正序数组的中位数(2/100)-一一网

这是我参与更文挑战的第9天，活动详情查看：更文挑战

题目描述

寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

leetcode-cn.com/problems/me…

// 示例1 
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
// 示例2 
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
输出：[1,2]
// 示例3
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

复制代码

解题分析

1. 暴力枚举

直接直向思维，两个有序的数组，求中位数。把他变成一个有序的数组就行了。

然后求中位数，当一组数据的数量为奇数时， 中位数 = 数据[ 数据长度 / 2 ] 。

比如 [1,2,3,4,5]的中位数为 [1,2,3,4,5][Math.floor(5 / 2)] => [1,2,3,4,5][2] => 3

当一组数据的数量为偶数时， (中位数 = 数据[(数据长度 / 2)] + 数据[ (数据长度 / 2 - 1 )) / 2。

比如 [1,2,3,4,5,6]的中位数为([1,2,3,4,5,6][6 / 2] + [1,2,3,4,5,6][6 / 2 + 1]) / 2 => (4 + 3) / 2 => 3.5

直接上代码。

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    // 获取两个数组长度的和
    const n: number  = nums1.length + nums2.length
    // 合并并按从小到大排序两个数组
    const nums: number [] = [...nums1, ...nums2].sort((a, b) => b - a)
    // 如果合并后的数组长度是偶数，那就用最中间的两个数相加除以2返回，要么就用最中间的数
    if(n % 2 === 0 ) return (nums[n / 2] + nums[n / 2 - 1]) / 2
    else return nums[Math.floor(n / 2)]
};
复制代码

2. 双指针

快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如fast每次增长两个，slow每次增长一个。

因为知道传入的两个数组是有序的，我们可以使用双指针减少遍历次数。

假设传入数组a为[1,3]，数组b为[2,4,5]。

我们遍历的次数为 Math.floor((a.length + b.length) /2) 

指针a 在 a数组的[0]下标1处
指针b 在 b数组的[0]下标2处

遍历第一次

1   3  
*
2   4   5
*

这时候我们判断，指针a没走完a数组并且 指针a的值小于指针b时，保存指针a的值为当前值并走一步，不然那就让指针b走。

我们看到 指针a没走完数组a，并且小于指向下标[0]值为2的指针b，继续走指针a。
这时当前值为1

遍历第二次

1   3  
    *
2   4   5
*

这时候我们继续判断
指向下标[1]值为3的 指针a，他已经比指向下标[0]值为2的指针b大了，那就让指针b继续跑路。
这时当前值为2

遍历第三次 

1   3  
    *
2   4   5
    *

还是一样的逻辑，3比4小且没跑完，走a。
这时当前值为3

[1,2,3,4,5] => 中位数3 
复制代码

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {

    const [n1, n2] = [nums1.length, nums2.length]
    const len = n1 + n2  //获取总长度来遍历
    let [preValue, curValue] = [-1, -1] //curValue为指针当前走的值，而preValue需要用来解偶数长度的数组中位数
    let [point1, point2] = [0, 0] // 指针a，b

    //只要循环一半
    for(let i =0; i<= Math.floor(len  /2); i++) {
        // 获取上次的值
        preValue = curValue
        // 指针a没走完数组a，并且 指针b走完数组b 或者 指针a所在的值没指针b所在的值大时，让指针a走一步，不然就让指针b走。
        if(point1 < n1 && (point2 >= n2 || nums1[point1] < nums2[point2])) {
            curValue = nums1[point1]
            point1++
        }
        else {
            curValue = nums2[point2]
            point2++
        }
    }


    if(len % 2 === 0) return (preValue + curValue) / 2
    else return curValue
};
复制代码