arrays - 将数组大小 n 分成 k 个相同大小的组

Question

我有一个大小为n的未排序数组，我需要找到k-1 个除数，因此每个子集的大小都相同（就像数组排序后一样）。

我用k-1=3看到了这个问题。我想我需要中位数的中位数，这将需要o(n)。但我认为我们应该这样做k次所以o(nk)。
我想了解为什么需要o(n logk)。

例如：我有一个未排序的整数数组，我想找到第k个除数，这是根据值将数组拆分为 k（相同大小）子数组的 k-1 个整数。
如果我有[1, 13, 6, 7, 81, 9, 10, 11]3=k 分隔符，则分割[7 ,11]到[1 6, 9 10 13 81]每个子集都大为 2 且相等的位置。

Answer 1

您可以使用分而治之的方法。首先，(k-1)/2使用中位数算法找到第 th 个除法器。接下来，使用所选元素将列表划分为两个子列表。在每个子列表上重复该算法以找到剩余的分隔符。

最大递归深度是O(log k)，每个级别的所有子列表的总成本是O(n)，所以这是一个O(n log k)算法。