题目描述
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
来源：Js 中 文 网 - 全球前端挚爱的技术成长平台 https://www.javascriptc.com/
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
难度：
- 难度：困难
- 支持语言：JavaScript、Java、Python
相关标签
相关企业
- 阿里
- 百度
- 腾讯
思路
首先了解一下 Median 的概念，一个数组中 median 就是把数组分成左右等分的中位数。
如下图：
这道题，很容易想到暴力解法，时间复杂度和空间复杂度都是O(m+n), 不符合题中给出O(log(m+n))时间复杂度的要求。
我们可以从简单的解法入手，试了一下，暴力解法也是可以被 Leetcode Accept 的. 分析中会给出两种解法，暴力求解和二分解法。
解法一 – 暴力 （Brute Force）
暴力解主要是要 merge 两个排序的数组（A，B）成一个排序的数组。
用两个pointer（i，j），i 从数组A起始位置开始，即i=0开始，j 从数组B起始位置， 即j=0开始.
一一比较 A[i] 和 B[j],
- 如果
A[i] <= B[j], 则把A[i]放入新的数组中，i 往后移一位，即i+1. - 如果
A[i] > B[j], 则把B[j]放入新的数组中，j 往后移一位，即j+1. - 重复步骤#1 和 #2，直到
i移到A最后，或者j移到B最后。 - 如果
j移动到B数组最后，那么直接把剩下的所有A依次放入新的数组中. - 如果
i移动到A数组最后，那么直接把剩下的所有B依次放入新的数组中.
Merge 的过程如下图。
时间复杂度： O(m+n) - m is length of A, n is length of B
空间复杂度： O(m+n)
解法二 – 二分查找 （Binary Search）
由于题中给出的数组都是排好序的，在排好序的数组中查找很容易想到可以用二分查找（Binary Search), 这里对数组长度小的做二分，
保证数组 A 和 数组 B 做 partition 之后
len(Aleft)+len(Bleft)=(m+n+1)/2 - m是数组A的长度， n是数组B的长度
对数组 A 的做 partition 的位置是区间[0,m]
如图：
下图给出几种不同情况的例子（注意但左边或者右边没有元素的时候，左边用INF_MIN，右边用INF_MAX表示左右的元素：
下图给出具体做的 partition 解题的例子步骤，
时间复杂度： O(log(min(m, n)) - m is length of A, n is length of B
空间复杂度： O(1) – 这里没有用额外的空间
关键点分析
- 暴力求解，在线性时间内 merge 两个排好序的数组成一个数组。
- 二分查找，关键点在于
- 要 partition 两个排好序的数组成左右两等份，partition 需要满足
len(Aleft)+len(Bleft)=(m+n+1)/2 - m是数组A的长度， n是数组B的长度 -
并且 partition 后 A 左边最大(
maxLeftA), A 右边最小（minRightA), B 左边最大（maxLeftB), B 右边最小（minRightB) 满足
(maxLeftA <= minRightB && maxLeftB <= minRightA)
有了这两个条件，那么 median 就在这四个数中，根据奇数或者是偶数，
奇数：
median = max(maxLeftA, maxLeftB)
偶数：
median = (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2
Js中文网 – 前端进阶资源教程 www.javascriptC.com,typescript 中文文档
Javascript中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js……等，以帮助开发者成长为愿景的社区
复杂度分析
- 时间复杂度：$O(log(min(m, n)))$
- 空间复杂度：$O(log(min(m, n)))$
代码
Java 实现
解法一 – 暴力解法（Brute force）
class MedianTwoSortedArrayBruteForce {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] newArr = mergeTwoSortedArray(nums1, nums2);
int n = newArr.length;
if (n % 2 == 0) {
// even
return (double) (newArr[n / 2] + newArr[n / 2 - 1]) / 2;
} else {
// odd
return (double) newArr[n / 2];
}
}
private int[] mergeTwoSortedArray(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] res = new int[m + n];
int i = 0;
int j = 0;
int idx = 0;
while (i < m && j < n) {
if (nums1[i] <= nums2[j]) {
res[idx++] = nums1[i++];
} else {
res[idx++] = nums2[j++];
}
}
while (i < m) {
res[idx++] = nums1[i++];
}
while (j < n) {
res[idx++] = nums2[j++];
}
return res;
}
}
/**
* @作者：windliang
* @链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/
*/
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] nums;
int m = nums1.length;
int n = nums2.length;
nums = new int[m + n];
if (m == 0) {
if (n % 2 == 0) {
return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
} else {
return nums2[n / 2];
}
}
if (n == 0) {
if (m % 2 == 0) {
return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
} else {
return nums1[m / 2];
}
}
int count = 0;
int i = 0, j = 0;
while (count != (m + n)) {
if (i == m) {
while (j != n) {
nums[count++] = nums2[j++];
}
break;
}
if (j == n) {
while (i != m) {
nums[count++] = nums1[i++];
}
break;
}
if (nums1[i] < nums2[j]) {
nums[count++] = nums1[i++];
} else {
nums[count++] = nums2[j++];
}
}
if (count % 2 == 0) {
return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
} else {
return nums[count / 2];
}
}
//还有另一种解法
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int left = (n + m + 1) / 2;
int right = (n + m + 2) / 2;
//将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
}
private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
//让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
if (len1 == 0) return nums2[start2 + k - 1];
if (k == 1) return Math.min(nums1[start1], nums2[start2]);
int i = start1 + Math.min(len1, k / 2) - 1;
int j = start2 + Math.min(len2, k / 2) - 1;
if (nums1[i] > nums2[j]) {
return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
}
else {
return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}
}
JavaScript 实现
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function (nums1, nums2) {
// 归并排序
const merged = [];
let i = 0;
let j = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
merged.push(nums1[i++]);
} else {
merged.push(nums2[j++]);
}
}
while (i < nums1.length) {
merged.push(nums1[i++]);
}
while (j < nums2.length) {
merged.push(nums2[j++]);
}
/* 来源：Js 中 文 网 - 全球前端挚爱的技术成长平台 https://www.javascriptc.com/ */
const { length } = merged;
return length % 2 === 1
? merged[Math.floor(length / 2)]
: (merged[length / 2] + merged[length / 2 - 1]) / 2;
};
复杂度分析
- 时间复杂度：$O(max(m, n))$
- 空间复杂度：$O(m + n)$
解法二 – 二分查找（Binary Search)
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：前端中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js
* 二分解法
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function (nums1, nums2) {
// make sure to do binary search for shorten array
if (nums1.length > nums2.length) {
[nums1, nums2] = [nums2, nums1];
}
const m = nums1.length;
const n = nums2.length;
let low = 0;
let high = m;
while (low <= high) {
const i = low + Math.floor((high - low) / 2);
const j = Math.floor((m + n + 1) / 2) - i;
const maxLeftA = i === 0 ? -Infinity : nums1[i - 1];
const minRightA = i === m ? Infinity : nums1[i];
const maxLeftB = j === 0 ? -Infinity : nums2[j - 1];
const minRightB = j === n ? Infinity : nums2[j];
/* 来源：Js 中 文 网 - 全球前端挚爱的技术成长平台 https://www.javascriptc.com/ */
if (maxLeftA <= minRightB && minRightA >= maxLeftB) {
return (m + n) % 2 === 1
? Math.max(maxLeftA, maxLeftB)
: (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
} else if (maxLeftA > minRightB) {
high = i - 1;
} else {
low = low + 1;
}
}
};
class MedianSortedTwoArrayBinarySearch {
public static double findMedianSortedArraysBinarySearch(int[] nums1, int[] nums2) {
// do binary search for shorter length array, make sure time complexity log(min(m,n)).
if (nums1.length > nums2.length) {
return findMedianSortedArraysBinarySearch(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
int lo = 0;
int hi = m;
while (lo <= hi) {
// partition A position i
int i = lo + (hi - lo) / 2;
// partition B position j
int j = (m + n + 1) / 2 - i;
int maxLeftA = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
int minRightA = i == m ? Integer.MAX_VALUE : nums1[i];
int maxLeftB = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
int minRightB = j == n ? Integer.MAX_VALUE : nums2[j];
if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
// total length is even
/* 来源：Js 中 文 网 - 全球前端挚爱的技术成长平台 https://www.javascriptc.com/ */
if ((m + n) % 2 == 0) {
return (double) (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
} else {
// total length is odd
return (double) Math.max(maxLeftA, maxLeftB);
}
} else if (maxLeftA > minRightB) {
// binary search left half
hi = i - 1;
} else {
// binary search right half
lo = i + 1;
}
}
return 0.0;
}
}
Python3 实现
- 这道题如果时间复杂度没有限定在 O(log(m+n))O(log(m+n))，我们可以用 O(m+n)O(m+n) 的算法解决，用两个指针分别指向两个数组，比较指针下的元素大小，一共移动次数为 (m+n + 1)/2，便是中位数。
-
首先，我们理解什么中位数：指的是该数左右个数相等。
- 比如：odd : [1,| 2 |,3]，2 就是这个数组的中位数，左右两边都只要 1 位；
-
even: [1,| 2, 3 |,4]，2,3 就是这个数组的中位数，左右两边 1 位；
-
那么，现在我们有两个数组：
num1: [a1,a2,a3,...an]nums2: [b1,b2,b3,...bn][nums1[:left1],nums2[:left2] | nums1[left1:], nums2[left2:]] -
只要保证左右两边 个数 相同，中位数就在 | 这个边界旁边产生。
-
如何找边界值，我们可以用二分法，我们先确定
num1取m1个数的左半边，那么num2 取 m2 = (m+n+1)/2 - m1的左半边，找到合适的 m1，就用二分法找。 - 当
[ [a1],[b1,b2,b3] | [a2,..an],[b4,...bn] ] -
我们只需要比较 b3 和 a2 的关系的大小，就可以知道这种分法是不是准确的！
-
例如：我们令：
nums1 = [-1,1,3,5,7,9]
nums2 =[2,4,6,8,10,12,14,16]
- 当
m1 = 4,m2 = 3,它的中位数就是median = (num1[m1] + num2[m2])/2 -
时间复杂度：O(log(min(m,n)))O(log(min(m,n)))
-
对于代码中边界情况，大家需要自己琢磨。
# @作者：powcai
# @链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/shuang-zhi-zhen-by-powcai/
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
n1 = len(nums1)
n2 = len(nums2)
if n1 > n2:
return self.findMedianSortedArrays(nums2,nums1)
k = (n1 + n2 + 1)//2
left = 0
right = n1
while left < right :
m1 = left +(right - left)//2
m2 = k - m1
if nums1[m1] < nums2[m2-1]:
left = m1 + 1
else:
right = m1
m1 = left
m2 = k - m1
c1 = max(nums1[m1-1] if m1 > 0 else float("-inf"), nums2[m2-1] if m2 > 0 else float("-inf") )
if (n1 + n2) % 2 == 1:
return c1
c2 = min(nums1[m1] if m1 < n1 else float("inf"), nums2[m2] if m2 <n2 else float("inf"))
return (c1 + c2) / 2
# @作者：ltzp
# @链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/hen-hao-li-jie-de-si-lu-by-ltzp/
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
res = 0.0
# 来源：Js 中 文 网 - 全球前端挚爱的技术成长平台 https://www.javascriptc.com/
new_array = []
m = len(nums1)
n = len(nums2)
length = m + n
mid = 0
if length & 1:
mid = int(length//2)
else:
mid = int(length/2)
i,j = 0,0
while len(new_array) -1 < mid:
if i < m and j < n :
if nums1[i] < nums2[j]:
new_array.append(nums1[i])
i+=1
continue
if nums1[i] >= nums2[j]:
new_array.append(nums2[j])
j+=1
continue
if i == m and j < n:
while j < n and len(new_array) -1 < mid:
new_array.append(nums2[j])
j+=1
if i < m and j == n:
while i < m and len(new_array) -1 < mid:
new_array.append(nums1[i])
i+=1
if length & 1:
res = new_array[mid]
else:
res = (new_array[mid-1] + new_array[mid])/2.0
return res
# 作者：yinchuan
# 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/tong-su-yi-dong-shi-xian-qi-lai-ye-jian-dan-de-si-/
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
length = len(nums1) + len(nums2)
i = 0 # 循环次数
pre = None # 前一个弹出的数，length为偶数会用到
cur = None
while i < length // 2 + 1:
n1 = nums1[-1] if nums1 else -float('inf')
n2 = nums2[-1] if nums2 else -float('inf')
pre = cur
cur = nums1.pop() if n1 > n2 else nums2.pop()
i += 1
result = cur
if length % 2 == 0:
result = (result + pre) / 2
return result
其他
- 原题leetcode链接：4.median-of-two-sorted-arrays – https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
- 合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台
- 说明：leetcode 题解 | 每日一题🔥 所有题目并非全部为本人解答，部分为在复习学习中整理提取其他解题作者的优秀笔记，便于大家学习共同进步，如有侵权，请联系删除。
更多题解可以访问我的 Js中文网 – 码农周刊 仓库：https://github.com/meibin08/free-programming-books， 一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发，我想请你帮我两个小忙：
- 把这篇文章分享给你的朋友 / 交流群，让更多的人看到，一起进步，一起成长！
- 关注公众号 「画漫画的程序员」，公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有，如若转载，请注明出处
转载请注明：文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com
微信扫一扫 
admin 
