4. Median of Two Sorted Arrays
4. Median of Two Sorted Arrays
题目
Given two sorted arrays nums1
and nums2
of size m
and n
respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n))
.
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6
题目大意
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
解题思路
给出两个有序数组,要求找出这两个数组合并以后的有序数组中的中位数。要求时间复杂度为 O(log (m+n))。
这一题最容易想到的办法是把两个数组合并,然后取出中位数。但是合并有序数组的操作是
O(m+n)
的,不符合题意。看到题目给的log
的时间复杂度,很容易联想到二分搜索。由于要找到最终合并以后数组的中位数,两个数组的总大小也知道,所以中间这个位置也是知道的。只需要二分搜索一个数组中切分的位置,另一个数组中切分的位置也能得到。为了使得时间复杂度最小,所以二分搜索两个数组中长度较小的那个数组。
关键的问题是如何切分数组 1 和数组 2 。其实就是如何切分数组 1 。先随便二分产生一个
midA
,切分的线何时算满足了中位数的条件呢?即,线左边的数都小于右边的数,即,nums1[midA-1] ≤ nums2[midB] && nums2[midB-1] ≤ nums1[midA]
。如果这些条件都不满足,切分线就需要调整。如果nums1[midA] < nums2[midB-1]
,说明midA
这条线划分出来左边的数小了,切分线应该右移;如果nums1[midA-1] > nums2[midB]
,说明 midA 这条线划分出来左边的数大了,切分线应该左移。经过多次调整以后,切分线总能找到满足条件的解。假设现在找到了切分的两条线了,
数组 1
在切分线两边的下标分别是midA - 1
和midA
。数组 2
在切分线两边的下标分别是midB - 1
和midB
。最终合并成最终数组,如果数组长度是奇数,那么中位数就是max(nums1[midA-1], nums2[midB-1])
。如果数组长度是偶数,那么中间位置的两个数依次是:max(nums1[midA-1], nums2[midB-1])
和min(nums1[midA], nums2[midB])
,那么中位数就是(max(nums1[midA-1], nums2[midB-1]) + min(nums1[midA], nums2[midB])) / 2
。图示见下图:
代码
var findMedianSortedArrays = function (nums1, nums2) {
if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
let x = nums1.length;
let y = nums2.length;
let low = 0,
high = x;
while (low <= high) {
const partitionX = (high + low) >> 1;
const partitionY = ((x + y + 1) >> 1) - partitionX;
const maxX =
partitionX == 0 ? Number.NEGATIVE_INFINITY : nums1[partitionX - 1];
const maxY =
partitionY == 0 ? Number.NEGATIVE_INFINITY : nums2[partitionY - 1];
const minX =
partitionX == nums1.length ? Number.POSITIVE_INFINITY : nums1[partitionX];
const minY =
partitionY == nums2.length ? Number.POSITIVE_INFINITY : nums2[partitionY];
if (maxX <= minY && maxY <= minX) {
const lowMax = Math.max(maxX, maxY);
if ((x + y) % 2 == 1) return lowMax;
return (lowMax + Math.min(minX, minY)) / 2;
} else if (maxX < minY) {
low = partitionX + 1;
} else high = partitionX - 1;
}
};
相关题目
- [🔒 Median of a Row Wise Sorted Matrix](https://leetcode.com/problems/median-of-a-row-wise-sorted-matrix)