Median of Two Sorted Arrays Leetcode #4 题解[C++]
题目来源
https://leetcode.com/problems/median-of-two-sorted-arrays/description/
题意解析
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)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
给出两个排好了序的数组, 求出这两个数组的中位数, 要求时间复杂度为O(log(m+n)).
解题思路
这道题想了很久都没有做出来, 想到的最快方法也是O((m-n)log(m+n)), 后来参考了讨论区的一份帖子才最终AC,
这里大概讲一下帖子所提供的思路.
中位数本身的含义就是它之前的数和它之后的数一样多. 因此, 想通了这一点, 我们就能把问题简化的多, 我们像下面这样把所有数割成左右两部分, 使得左边的数等于右边的. 并且满足max(left_part) <= min(right_part)
.
left_part | right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
这样一来, 利用A[i-1], A[i], B[j-1], B[j]这几个数我们便能求出所需的中位数.
不失一般性, 假设len(A)=m < len(B)=n, 令 i 取[0,m], 令 j 取(m + n + 1)/2 - i, 这样就能保证左右两边的数字总数相同.
接下来只需要设法满足max(left_part) <= min(right_part)
即可. 既然已经知道了 i 的取值范围, 我们通过二分查找来寻找满足这一条件的 i 的值即可.
代码实现
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
if (n < m) return findMedianSortedArrays(nums2, nums1);
int i, j,max_left,min_right;
int imin = 0;
int imax = m;
int half_len = (m + n + 1) / 2;
while (imin <= imax) {
i = (imin + imax) / 2;
j = half_len - i;
//i should be bigger
if (i<m&&nums2[j - 1]>nums1[i]) imin = i + 1;
//i should be smaller
else if (i > 0 && nums1[i - 1] > nums2[j]) imax = i - 1;
//We have found i that satisfied our requirement.
else {
//Don't forget to consider edge conditions.
if (i == 0) max_left = nums2[j - 1];
else if (j == 0) max_left = nums1[i - 1];
else max_left = max(nums1[i - 1], nums2[j - 1]);
//If total nums is odd then only need to return max_left.
if ((n + m) & 1) return max_left;
if (i == m) min_right = nums2[j];
else if (j == n) min_right = nums1[i];
else min_right = min(nums1[i], nums2[j]);
return double(min_right + max_left) / 2.0;
}
}
}
};
推荐阅读
-
【LeetCode】4. Median of Two Sorted Arrays
-
LeetCode 4. 两个排序数组的中位数 Median of Two Sorted Arrays
-
LeetCode算法系列:4、Median of Two Sorted Arrays
-
4. Median of Two Sorted Arrays
-
4. Median of Two Sorted Arrays
-
【leetcode】4. Median of Two Sorted Arrays
-
【leetcode阿里题库】4. Median of Two Sorted Arrays
-
Median of Two Sorted Arrays(C++)
-
LeetCode 4. Median of Two Sorted Arrays
-
从0开始的leetCode:Median of Two Sorted Arrays