题目来源:
题目难度:Hard
题目
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
1 | nums1 = [1, 3] |
Example 2:
1 | nums1 = [1, 2] |
解答1[Java]
1 | public double findMedianSortedArrays(int[] nums1, int[] nums2) { |
时空复杂度分析
时间复杂度:$O((m+n)log(m+n))$
空间复杂度:$O(m+n)$
解法2[Java]
1 | class Solution { |
算法分析
核心思想是二分查找。
假设 A 数组是长度为 4,B 数组长度为 6,那么把 A 数组和 B 数组混合,然后重新排序,称之为数组 C。那么数组 C 的前半部分,必定由 A 中的若干个数和 B 中的若干个数组成。
时空复杂度分析
时间复杂度:$O(log(min(m,n))$
空间复杂度:$O(1)$
拓展
思考:如果是求三个有序数组的中位数呢?