2回答

liuyubobobo

2019-12-11

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

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

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

===========

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

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

==========

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

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

继续加油！：）

1

1

安然2015

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

2019-12-11

共1条回复

安然2015

提问者

2019-12-11

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

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

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

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

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

0

1

liuyubobobo

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

2019-12-12

共1条回复