[LeetCode]4. Median of Two Sorted Arrays

Problem

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
2
3
4
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution

解析

题目给出两个有序数组,大小分别为m和n,计算两个有序数组的中位数。时间复杂度要求O( log(m+n) ).同时假设数组1和数组2不可能同时为空。

最原始的想法是使用归并排序的merge函数,生成一个有序数组,然后再计算中位数。因为中位数的位置和m+n的奇偶性相关。如果为奇数,中文数下标为(m+n)/2;如果是偶数,中位数和两个数有关,下标依次为:(m+n-1)/2, (m+n)/2。比如[1,2,3],中位数是2;[1,2,3,4],中位数是2.5。但是这种做法时间复杂度比较高,O(m+n)。不符合时间复杂度要求。

正确解法是使用二分查找。

数组1大小为m,数组2大小为n;m和n的大小不一定,可能数组1容量大,也可能数组2容量大,也可能两个数组长度相同。这里使用一个trick,直接查找在merged后第k大的数,直接找到和中位数相关的数。因为m+n奇偶性不一定,我们直接查找(m+n+1)/2, (m+n+2)/2大的数。可以验证,如果(m+n)是奇数,(m+n+1)/2和(m+n+2)/2大小相等[(m+n+2)/2 = (m+n+1 + 1)/2 = (m+n+1)/2 + 1/2 = (m+n+1)/2];如果是偶数,那么(m+n+1)/2和(m+n+2)/2正好是和中位数相关的两个数。

接下来的问题就是,给定一个数k如何找到merged后的第k个数。先考虑边界情况:

  • 如果一个数组为空,那么在第k个数一定在另一个数组里[因为题题目要求,两个数组不能同时为空,所以一定在另一个数组里]
  • 如果k为1,那么结果一定是两个数组中第一个元素较小的那一个。

一般情况,两个数组都不为空,同时k也不为1,那么如何在两个有序数组中找到第k个数呢?二分查找,如何应用在两个数组里?这里,采用一种独特的二分查找方法,对查找数k进行二分, 一般情况下是对有序数组范围进行二分;(接下来的问题就是边界的变化)分别在两个数组里找第k/2个数,如果第k/2个数的位置超出了数组范围,返回一个无效值;如果有效,比较两个数组中的查找结果midVal1和midVal2:如果midVal1 < midVal2,那么第k大的数一定不在midVal1的左边,所以,我们对数组1的有效范围进行缩小,同时在数组1的剩余元素和数组2中继续查找,查找第k-k/2个数[抛去了k/2个元素,这些元素一定是在第k个元素之前,所以需要查找的数也要对应减小;另外,这里必须使用k-k/2,不能直接使用k/2,因为k有可能是偶数,k/2的结果一定是整型,导致结果出错]。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
int left = (m + n + 1)/2, right = (m + n + 2)/2;

return (find(nums1, 0, nums2, 0, left) + find(nums1, 0, nums2, 0, right))/2.0;
}
int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k){
if (i >= nums1.size()) return nums2[j + k - 1];
if (j >= nums2.size()) return nums1[i + k - 1];
if (k == 1) return min(nums1[i], nums2[j]);

int midVal1 = (i + k / 2 - 1 >= nums1.size() ? INT_MAX : nums1[i + k/2 - 1]);
int midVal2 = (j + k/2 -1 >= nums2.size() ? INT_MAX : nums2[j + k / 2 - 1]);

if (midVal1 < midVal2)
return find(nums1, i + k/2, nums2, j, k - k/2);
else
return find(nums1, i, nums2, j + k/2, k - k/2);
}
};

Reference

https://www.cnblogs.com/grandyang/p/4465932.html

您的支持就是我更新的最大动力!谢谢!