题目
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2
请你找出并返回这两个正序数组的中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
规则示例
规则:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10的6次方 <= nums1[ i ], nums2[ i ] <= 10的6次方
示例 1:
输入:nums1 = [1,3], nums2 = [2]
输出:2
解释:合并数组 = [1, 2, 3] ,中位数 2
示例 2:
输入:nums1 = [1, 2], nums2 = [3, 4]
输出:2.5
解释:合并数组 = [1, 2, 3, 4] ,中位数(2 + 3) / 2 = 2.5
解题分析一,时间复杂度为O(m+n)的解法
解题思路:将两个数组合并为一个数组,再求其中的中位数
我们以两个数组为例
nums1 = [1,4,5,7]
nums2 = [2,3,6,8]
知道两个数组的长度,我们可以构建一个新数组array用于存储他们
之后计算出这个新数组的中位数即可
中位数规则,合并数组长度为
注意:C#中,默认向下取整
偶数:( array[array.Length / 2] + array[array.Length / 2 - 1] ) / 2
奇数:array[array.Length / 2]
解题一,时间复杂度为O(m+n)的解法
public static float FindMedianSortedArrays(int[] nums1, int[] nums2)
{
//答题处
float midNum = 0;
//声明一个新数组,长度是两个数组之和
int[] array = new int[nums1.Length + nums2.Length];
//声明两个数组的索引,用于取出两个数组中的值进行比较,如果数组为空则索引为-1
//-1表示某个数组已经遍历完成
int nums1Index = nums1.Length == 0 ? -1 : 0;
int nums2Index = nums2.Length == 0 ? -1 : 0;
//为新数组放入内容
for (int i = 0; i < array.Length; i++)
{
//数组1已经遍历完
if (nums1Index == -1)
{
//数组1遍历完了,直接放入数组2的内容
array[i] = nums2[nums2Index];
//数组2索引+1,如果超过长度则为-1表示遍历完成
nums2Index = nums2Index + 1 >= nums2.Length ? -1 : nums2Index + 1;
}
//数组2已经遍历完
else if (nums2Index == -1)
{
//数组2遍历完了,直接放入数组1的内容
array[i] = nums1[nums1Index];
//数组1索引+1,如果超过长度则为-1表示遍历完成
nums1Index = nums1Index + 1 >= nums1.Length ? -1 : nums1Index + 1;
}
//数组1元素小于数组2元素 放入新数组
else if ( nums1[nums1Index] <= nums2[nums2Index])
{
//放入数组1的内容
array[i] = nums1[nums1Index];
//数组1索引+1,如果超过长度则为-1表示遍历完成
nums1Index = nums1Index + 1 >= nums1.Length ? -1 : nums1Index + 1;
}
//数组2元素小于数组1元素 放入新数组
else
{
//放入数组2的内容
array[i] = nums2[nums2Index];
//数组2索引+1,如果超过长度则为-1表示遍历完成
nums2Index = nums2Index + 1 >= nums2.Length ? -1 : nums2Index + 1;
}
}
//计算中位数
//如果是偶数,左右两个数算平均值
if (array.Length % 2 == 0)
midNum = (array[array.Length / 2] + array[array.Length / 2 - 1]) / 2f;
else//如果是奇数,直接取出中位数
midNum = array[array.Length / 2];
return midNum;
}
我们已经使用了一种最容易理解的方法将此题完成,但是并不符合题目要求!题目要求的是需要让我们使用时间复杂度为O(log (m+n)) 的算法完成此题。
那么为什么我们还要做解法一呢?因为它可以帮助我们理解下一种解法!
从解法一中我们应该获取到的有用信息:
1.中位数的计算方式
奇数:直接取中间数
偶数:用中间两个数 / 2
2.通过移动两个数组的当前索引位置取出值
解题分析二,时间复杂度为O(m+n)的解法
解题思路:不用合并新数组,只是移动两个数组的索引寻找目标值
我们以两个数组为例
nums1 = [1,4,5,7],length = m
nums2 = [2,3,6,8],length = n
从解法一我们看出,其实我们没有必要去将两个数组真正合并成一个新数组来进行处理!我们只需要找到中位数在哪里就可以了。
我们已知的信息:
1.两个数组的长度 m 和 n
2.中位数的位置必会执行的计算
m + n / 2
m + n 为奇数:
m + n / 2 刚好为中位数索引
m + n 为偶数:
左数索引 = left = m + n / 2 - 1
右数索引 = right = m + n / 2
那我们完全可以利用这些已知信息来实现一个不用合并数组,只是移动两个数组的当前索引的算法来获取到中位数
解题二,时间复杂度为O(m+n)的解法
解法二相对解法一,空间复杂度更低,因为我们没有分配新的数组。
虽然时间复杂度同为m+n,但是遍历的次数更少了,因此解法二相对解法一性能表现更好。
通过以上两种解法,我们都还没有达到要求:
算法的时间复杂度应该为 O(log (m+n))
因此我们继续解题,结合目前已有的线索来寻求更优解
解题分析三,时间复杂度为O(log(m+n))的解法
解题思路:看到log,想到2分查找
分析1:
我们的目的其实是找到中位数索引,所以是否合并数组其实不重要
如何获得中位数索引,从解题一种我们知道
m + n 为奇数:( m + n ) / 2
m + n 为偶数:( m + n ) / 2 ,( m + n ) / 2 - 1
奇数取出索引( m + n ) / 2 对应的值就是中位数
偶数取出索引为( m + n ) / 2 和( m + n ) / 2 - 1 对应的值 除以 2就是中位数
分析2:
既然我们可以明确得到中位数索引
那么这道题就可以转化为寻找两个有序数组中的第 k 小的数
k的值为( m + n ) / 2 或( m + n ) / 2 + 1
注意:之前我们( m + n ) / 2 - 1是计算的索引,索引是从0开始 所以减1
现在我们这里的k是第几个数,是从1开始计数 所以加1
解法二中,我们一次遍历就相当于去掉了一个不可能的中位数值,相当于在逐个排除!
因为题目的规则是有序的数组,所以我们完全可以一半一半的排除
比如我们现在要找到第 k 小的数,我们可以每次循环排除掉 k / 2 个数
我们以两个数组为例
nums1 = [1,4,5,7],length = m = 4
nums2 = [2,3,6,8],length = n = 4
我们需要找到
1.第 (4 + 4)/ 2 = 4 小的数
2.第 (4 + 4)/ 2 + 1 = 5 小的数
首先来找第 4 小的数,我们采用折半排除法
从图中我们可以看出4是大于3的,所以下面那个数组的2和3应该在4之前,因此我们可以排除下方数组的2,3两个元素。(看上图)
将1457和68作为两个新的数组进行比较
灰色表示已经排除掉的数组(看下图)
由于我们已经排除掉了2个数字,也就是说排除的2个数字一定是在前面的,所以两个新数组只需要找到第 2 小的数字就可以了(4-2=2),也就是k = 2,那么同样我们折半排除 k / 2 = 1,比较 1 - 1 = 0 个数字(看上图)
1 < 6 那么证明 1 是在前面的,排除掉(如下图)
将457和68作为两个新的数组进行比较
由于又排除了1个数字,所以两个新数组只需要找到第 1 小的数字就可以了(2-1=1),也就是k = 1,由于此时k已经等于1了,无需再折半,只要比较了这一次,那证明我们已经找到目标值了。
4 < 6,因此第4小的数字是 4 !我们完成了找第 4 小的数
那么我们可以用同样的方法折半排除法找到 第 5 小的数
关键步骤:
1.折半 k / 2
2.比较两个数组第 k / 2 - 1个数
3.k = 1时是最后一次比较出结果
通过一个递归函数来达到每次折半排除
分析3:
通过分析2,我们已经可以利用折半排除法,找到对应第 n 小的数字了。
我们接着来思考一下特殊情况,当k折半后,某一个数组过短,长度小于了 k / 2 - 1
当 k / 2 - 1 = 1 时,上面的数组长度是1,我们只要此时将箭头指向它的末尾就行了,这种情况下,上面也不会发生越界,并且很快上面的数组就会被排除(如下图)
当一个数组全部被排除掉,那么我们可以直接取另外一个数组当中对应位置的数值就是我们想要找到的 第 4 个最小的值了
关键信息:
1.k / 2 > 数组长度,就使用数组长度进行计算
2.一个数组用完了,直接返回另一个数组第 n 个最小的数
解题三,时间复杂度为O(log(m+n))的解法
为了避免奇偶判断,我们将其合并处理
在递归中处理越界判断以及数组用完后,直接返回另一个数组中第k小个数的结果
END