0004 寻找两个正序数组的中位数 - Hero · 算法 · Leetcode

题目地址(0004. 寻找两个正序数组的中位数 )

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

JS实现(粗暴版)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  const combinedArr = nums1.concat(nums2).sort((a, b) => a - b);
  const halfLen = combinedArr.length / 2;
  if (Number.isInteger(halfLen)) {
    return (combinedArr[halfLen - 1] + combinedArr[halfLen]) / 2;
  } else {
    return combinedArr[Math.floor(halfLen)];
  }
};

JS实现(归并排序 粗暴版)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  const combinedArr = [];

  while (nums1.length > 0 || nums2.length > 0) {
    if (nums1.length === 0) {
      combinedArr.push(nums2.shift());
    } else if (nums2.length === 0) {
      combinedArr.push(nums1.shift());
    } else if (nums1[0] < nums2[0]) {
      combinedArr.push(nums1.shift());
    } else {
      combinedArr.push(nums2.shift());
    }
  }

  const halfLen = combinedArr.length / 2;
  if (Number.isInteger(halfLen)) {
    return (combinedArr[halfLen - 1] + combinedArr[halfLen]) / 2;
  } else {
    return combinedArr[Math.floor(halfLen)];
  }
};
Hero > 算法 > Leetcode
#Hero #算法 #Leetcode
0004 寻找两个正序数组的中位数 - Hero · 算法 · Leetcode
https://wanmeishijie.xyz/notes/hero/algo/leetcode/0004 寻找两个正序数组的中位数/
作者
源
发布于
2023年12月30日
许可协议