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
4nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
1
2
3
4nums1 = [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 | class Solution { |