Median of k Sorted Arrays 头条面试题 （leetcode 4 变式题）

Question

K个超长有序数组，求中位数 要求用二分法

请问波波老师 这个您能给出一些思路吗，我看了您的leetcode仓库，leetcode4 Median of two Sorted Arrays，您用的二分法 。可是我不知道如果是k个数组 该怎么办

Answer 1

liuyubobobo 2019-12-11 08:37:53

大体思路是：首先求出 k 个数组的中位数。这 k 个中位数中，最小的中位数所在的数组的左边的元素，和最大的中位数所在数组的右边的元素，都可以扔掉。

为了保证原数组的中位数和扔掉一些数字以后的中位数是一样的。实际扔掉的两边的数字，应该是一样的。假设最小中位数左边有 a 个元素，最大中位数右边有 b 个元素，实际应该左右两边都扔掉min(a, b)个元素。

不管怎样，经过这样的操作，问题的规模变小了（元素变少了）。剩下的数组继续这样进行。

===========

另外一个思路是，可以求 k 个数组的第 p 大元素。根据 k 个数组的元素总数，可以求出对于中位数，p 是多少。

之后，就可以每次求出每个数组的第 p 大元素。之后，最小的那个地 p 大元素左边的所有元素，和最大的第 p 大元素右边的所有元素都可以扔掉。此时，不需要顾及左右两边都要扔相同元素的问题。但是，每次扔完以后，p 要更新。（根据左边扔掉多少。）

==========

整体思路是这样的，但是这个问题实现起来，需要处理的细节也很多。如果你看了我的代码仓，可以看到，k = 2 的时候，也需要处理很多边界条件。

另外一个优化是，可以将 k 个中位数放在一个有序树中（比如红黑树），这样可以快速取出其中的最大值和最小值。

继续加油！：）

• 提问者 安然2015 #1

  是否可以这样思考呢，波波老师，您看看可不可行
  
  问题转化为 求k个数组里 第m大的数。
  
  我想到一个办法，二分  int最小值到 最大值（-2^31   -    2^31-1），然后 去 k个数组里，去寻找  此数 （比如说2^30）应该放在的索引（二分法）， 只要 所有比该数小的个数达到了m个，就可以了。 如果多于m个，那代表 我选的那个数大了。反之 ，小了。  然后继续二分下去。
  
  
  那么复杂度，最多是 31logN（N为所有数组里的数字个数和）。
  
  以上是我的一个思路，不知道对不对，还请您看看

Answer 2

提问者 安然2015 2019-12-11 14:18:56

是否可以这样思考呢，波波老师，您看看可不可行

问题转化为 求k个数组里 第m大的数。

我想到一个办法，二分  int最小值到 最大值（-2^31   -    2^31-1），然后 去 k个数组里，去寻找  此数 （比如说2^30）应该放在的索引（二分法）， 只要 所有比该数小的个数达到了m个，就可以了。 如果多于m个，那代表 我选的那个数大了。反之 ，小了。  然后继续二分下去。

那么复杂度，最多是 31logN（N为所有数组里的数字个数和）。

以上是我的一个思路，不知道对不对，还请您看看

• liuyubobobo #1

  大赞！很好的思路，完全可行！：）