题目描述
给定两个大小为 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 == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= 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