LeetCode力扣_第四题_两正序数组组合的中位数

2021-07-15 20:54 作者:啥也不会的小噢 0人读过 | 我要投稿

题目：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

例子：nums1=[1,2],nums2=[3,4],那么中位数就是2.5。假如一个nums为空，那么中位数就是另外一数组的中位数。

答：首先最暴力、直接的解法就是合并数组，再排序求中位数。

这种解法在Python中实现比较简单，看下代码块：

利用数组的一些方法可以轻松完成算法实现。在力扣上的计算速度和内存占用都还行。但是在时间和空间复杂度上还是有待商榷的（ps：还未学习相关概念）。

接下来介绍在力扣官方解答中的解答：

一、二分查找法

首先要明白的就是上述的暴力解法是遍历了所有数字的。而二分查找法的优点就是去掉了一些数组片段，减少了多余的遍历工作。

一般来讲：对于两正序数组A、B分别为m、n项，其合并后的中位数是第（m+n）/2个【m+n为奇数】或第（m+n）/2个和第（m+n）/2+1个的平均值【m+n为偶数】，二分查找法的是令k=（m+n）/2或（m+n）/2+1，再在比较每个数组内的[k/2-1]项，这样就有最多2*（k/2-1）项的数比这两个数组中的[k/2-1]较小的项还小，下面就分情况来考虑：

当A[k/2-1]<B[k/2-1]时：那么可以的到A中的前[k/2-1]项数是一定在右边的，不可能是A+B中的中位数的，因此把A的前[k/2-1]项舍去。
当A[k/2-1]>B[k/2-1]时：同理舍去B的前[k/2-1]项。
当A[k/2-1]=B[k/2-1]时：这种情况其实舍去A、B中那个都无所谓，因为A、B中的前[k/2-1]项都是较小的，不可能是A+B的第k小的数。

那么这样就可以减少遍历片段以来节约时间，每次舍去一部分，舍去的那个数组的【0~k/2-1】项不在被遍历，因此遍历的数少了k/2个，那么k的值更新为k-k/2。那么下一步二分查找的时候就是更新后的k，比较新的A[k/2-1]和B[k/2-1]的大小，再舍去多余的片段。在这里因为去掉了k/2个，k的值逐渐减小，这样来二次划分会逐渐靠近中位数。即最开始的时候A+B的第k个。当k=1的时候，中位数也就是划分去掉后的两新数组的首项，比较其大小即最小的是第k小的数。

但是存在特殊情况，即A[k/2-1]和B[k/2-1]超界了，那么这个时候，就取对应的数组最后一个数，若是舍去的时候要舍去这个小数组，k值更新的时候去掉小数组的个数，而不是取掉k/2；A/B若有一个是空的，那么只需要考虑另外一个数组的第k个就行，那即A+B中第k小的数。

python代码如下：

看到官方的这个解答，佩服把算法代码化的实力，自己还需要多努力！！！这里就不画流程图了，主要解释下代码实现算法的思路：

这里是创建了一个函数获取的第k个数，函数的参数是由两数组的程度决定的，可以看到这里判别了数组的长度是奇数还是偶数，是奇数就是第k个数就是中位数，偶数是取中间两数的平均值。故会有上述代码的主函数段。k的值确定后，看getKelement（k）是怎么操作的？首先是创建了两索引index，再判断特殊情况，首先是两者空数组的情况，直接返回另外数组的第k个数；然后判断k是否更新到1了，是的话返回首项最小值。重点是正常的情况，每个数组创建一个新的索引，新的索引是之前的索引+k//2-1和数组右边界的最小值（出界的情况考虑进去了），第一步是可以理解的，就是第[k//2-1]项,然后比较大小，再根据情况更新k的值，就是k-k//2，之所以后面加1是数组索引是从0开始的。后面的index赋值也是同样的道理，因为从0~k//2-1都舍去了，就从k//2开始了。然后就继续二分了，这里我开始以为会重新创建数组，后来发现是我菜了，只是指针的范围往前走了就行。newindex后面的赋值因为从index开始取值了，故需要加上index。

二、划分数组

这里是最np的算法了，首先咱要理解中位数的定义了。

中位数是将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。

在这里我们要注意关键词长度相等，一个子集的元素总是大于或等于另外一个子集的元素；

这是这个算法的主要逻辑，也就是把A+B划分为两个子集，其中一个子集的最大值总是小于另外一个子集的最小值。且两子集的数字个数相同或数值小的子集多一个数。