给定两个大小分别为m和n的正序(从小到大)数组nums1和nums2。请你找出并返回这两个正序数组的中位数。
示例 1:
1 | 输入:nums1 = [1,3], nums2 = [2] |
示例 2:
1 | 输入:nums1 = [1,2], nums2 = [3,4] |
示例 3:
1 | 输入:nums1 = [0,0], nums2 = [0,0] |
示例 4:
1 | 输入:nums1 = [], nums2 = [1] |
示例 5:
1 | 输入:nums1 = [2], nums2 = [] |
提示:
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -106 <= nums1[i], nums2[i] <= 106
进阶:你能设计一个时间复杂度为O(log(m+n))的算法解决此问题吗?
排序后返回
虽然在leetcode上这题给出的难度是困难,但是我觉得做出来还是不难的:
- 因为两个数组是正序的,所以给两个数组排序只需O(m+n)的时间复杂度;
- 为了避免每个步骤都必须检查数组越界,我们在数组尾部设置一个哨兵值,这里哨兵值采用106+1;
code
1 | func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { |
分析
- 时间复杂度:O(m+n)
- 空间复杂度:O(m+n)
降低复杂度
以下分析来自官方解答
如何把时间复杂度降低到O(log(m+n)) 呢?如果对时间复杂度的要求有log,通常都需要用到二分查找,这道题也可以通过二分查找实现。
根据中位数的定义,当m+n是奇数时,中位数是两个有序数组中的第(m+n)/2个元素,当m+n是偶数时,中位数是两个有序数组中的第(m+n)/2个元素和第(m+n)/2+1个元素的平均值。因此,这道题可以转化成寻找两个有序数组中的第k小的数,其中k为(m+n)/2或(m+n)/2+1。
假设两个有序数组分别是A和B。要找到第k个元素,我们可以比较A[k/2−1]和B[k/2−1],其中/表示整数除法。由于A[k/2−1]和B[k/2−1]的前面分别有A[0..k/2−2]和B[0..k/2−2],即k/2−1个元素,对于A[k/2−1]和B[k/2−1]中的较小值,最多只会有(k/2−1)+(k/2−1)≤k−2个元素比它小,那么它就不能是第k小的数了。
因此我们可以归纳出三种情况:
- 如果A[k/2-1]<B[k/2-1],则比A[k/2-1]小的数最多只有A的前k/2-1个数和B的前k/2-1个数,即至多k-2个,因此A[k/2-1]不可能是第k个数,A[0]到A[k/2-1]也不可能是第k个数,可以全部排除;
- 如果A[k/2-1]>B[k/2-1],同理可以排除B[0]到B[k/2-1];
- 如果A[k/2-1]=B[k/2-1],也可以归结到第一种情况;
可以分析得,每次比较后可以排除k/2个数(譬如A[k/2-1]<=B[k/2-1],那么A[0]~A[k/2-1]都一定不是第k大的数),所以每次查找完需要更新k值,一般而言是k=k-k/2,有以下三种特殊情形需要特殊处理:
- 如果A[k/2-1]或者B[k/2-1]越界,那么我们可以选取数组中最后一个元素,对应的k值也应该减去排除的个数,而不是武断的减去k/2;
- 如果一个数组为空,说明该数组中的元素都被排除了,我们可以直接返回另一个数组中第k小的元素;
- 如果k=1,我们只要返回两个数组较小的首元素即可;
用一个例子说明上述算法。假设两个有序数组如下:
1 | A: 1 3 4 9 |
两个有序数组的长度分别是4和9,长度之和是13,中位数是两个有序数组中的第7个元素,因此需要找到第k=7个元素。
比较两个有序数组中下标为k/2−1=2的数,即A[2]和B[2],如下面所示:
1 | A: 1 3 4 9 |
由于A[2]>B[2],因此排除B[0]到B[2],即数组B的下标偏移(offset)变为3,同时更新k的值:k=k−k/2=4。
下一步寻找,比较两个有序数组中下标为k/2−1=1的数,即A[1]和B[4],如下面所示,其中方括号部分表示已经被排除的数。
1 | A: 1 3 4 9 |
由于A[1]<B[4],因此排除A[0]到A[1],即数组A的下标偏移变为2,同时更新k的值:k=k−k/2=2。
下一步寻找,比较两个有序数组中下标为k/2−1=0的数,即比较A[2]和B[3],如下面所示,其中方括号部分表示已经被排除的数。
1 | A: [1 3] 4 9 |
由于A[2]=B[3],根据之前的规则,排除A中的元素,因此排除A[2],即数组A的下标偏移变为3,同时更新k的值:k=k−k/2=1。
由于k的值变成1,因此比较两个有序数组中的未排除下标范围内的第一个数,其中较小的数即为第k个数,由于A[3]>B[3],因此第k个数是B[3]=4。
1 | A: [1 3 4] 9 |
代码如下:
1 | func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { |
分析
- 时间复杂度:O(log(m+n))
- 空间复杂度:O(1)
不过在leetcode上的运行时间并没有减少多少。。。