关于leetcode:LeetCode-第-4-号问题寻找两个正序数组的中位数

38次阅读

共计 837 个字符,预计需要花费 3 分钟才能阅读完成。

LeetCode 第 4 号问题:寻找两个正序数组的中位数

题目地址

https://leetcode-cn.com/probl…

题目形容

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

思路

暴力解决办法: 拼接后找中位数

代码一

const findMedianSortedArrays = function(nums1, nums2) {let arr=nums1.concat(nums2)// 合并两个数组
    arr.sort((a, b) => a - b)// 新数组从小到大排序
    let length = arr.length
    if(length%2==0){
        /**
         * 数组长度为偶数,输入两头两数之和的平均值
        */
        return (arr[length/2]+arr[length/2-1])/2
    }else{
        /**
         * 数组长度为奇数,输入两头数
        */
        return arr[(length-1)/2]
    }
};

代码二

代码起码的办法,工夫复杂度为 O((m + n)log(m + n))

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
const findMedianSortedArrays = function(nums1, nums2) {const arr = [...nums1, ...nums2].sort((a, b) => a - b);
    const {length} = arr;
    return length % 2 ? arr[Math.floor(length / 2)] : (arr[length / 2] + arr[length / 2 - 1]) / 2;
}

LeetCode 第 4 号问题:寻找两个正序数组的中位数

正文完
 0