原题地址:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

题目描述

给定两个大小为 mn有序 数组 nums1nums2

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))

你可以假设 nums1nums2 不会同时为空

示例

示例 1

  • nums1 = [1, 3]
  • nums2 = [2]
  • 则中位数是 2.0

示例 2

  • nums1 = [1, 2]
  • nums2 = [3, 4]
  • 则中位数是 (2 + 3)/2 = 2.5

构造输入输出

考虑到几种特殊的情况,本地写代码构造的输入输出可以如下:

let nums1 = [1, 3];
let nums2 = [2];
let nums1 = [1, 3];
let nums2 = [2];
let nums1 = [1, 2];
let nums2 = [3, 4];

注意可能存在负数的情况

let nums1 = [3];
let nums2 = [-2, -1]; 

注意可能存在的空数组情况

let nums1 = [];
let nums2 = [-3, -2, -1]; 

JavaScript 解题

js 写这个题如果是暴力还是很简单,数组拼接再排个序即可。

不过这存在很明显的问题,因为本身 nums1 和 nums2 都是有顺序的,拼接之后再排序有点得不偿失

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    let arr = nums1.concat(nums2);  // 数组拼接
    arr = arr.sort((a, b) => { return a - b }); // 数组排序
    const len = arr.length;
    const index = parseInt(len / 2); // 计算中间位置 index (如果是 偶数长度,则 index 并非中间)
    if (len % 2 !== 0) { 
        return arr[index].toFixed(1); // 如果是非偶数,直接返回中间即可(注意输出是 1.0)
    } else {
        return ((arr[index - 1] + arr[index]) / 2).toFixed(1);  // 偶数需要计算求平均值同时保留1位小数点
    }
};

结果

2.jpg