20201003
给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
进阶: 你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗?
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000
输入:nums1 = [], nums2 = [1]
输出:1.00000
输入:nums1 = [2], nums2 = []
输出:2.00000
提示:
抛砖引玉
思路
先暴力合并排序求解:
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
let arr = [...nums1, ...nums2],
len = arr.length,
index = Math.floor(len / 2)
if (len <= 1) return arr[0] || 0
arr.sort((a, b) => a - b)
if (len % 2) {
// 长度为奇数
return arr[index]
} else {
// 长度为偶数
return (arr[index] + arr[index - 1]) / 2
}
}
除了上面暴力的方法,还可以不用合并两个数组来处理本题
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
let len1 = nums1.length,
len2 = nums2.length
if (len1 > len2) return findMedianSortedArrays(nums2, nums1)
let len = len1 + len2
let start = 0,
end = len1
let partLen1, partLen2
while (start <= end) {
partLen1 = parseInt((start + end) / 2, 10)
partLen2 = parseInt((len + 1) / 2, 10) - partLen1
let L1 = partLen1 === 0 ? -Infinity : nums1[partLen1 - 1]
let L2 = partLen2 === 0 ? -Infinity : nums2[partLen2 - 1]
let R1 = partLen1 === len1 ? Infinity : nums1[partLen1]
let R2 = partLen2 === len2 ? Infinity : nums2[partLen2]
if (L1 > R2) {
end = partLen1 - 1
} else if (L2 > R1) {
start = partLen1 + 1
} else {
return len % 2
? Math.max(L1, L2)
: (Math.max(L1, L2) + Math.min(R1, R2)) / 2
}
}
}
[1]
题目:: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
[2]
公众号:前端小书童: http://qiniu.gaowenju.com/wechat-new.png