阵列大小n为k相同尺寸组

Question

我有一个未排序阵列大小Ñ的和我需要找到k-1个除数所以每子集是相同的尺寸（如数组进行排序之后） 。

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

例如：我有一个整数未排序的数组，我想要找到第k个整数，将数组按照它们的值拆分成k个（相同大小）子排列的第n个整数。
如果我有[1, 13, 6, 7, 81, 9, 10, 11] 3 = k分隔符是[7 ,11]分裂为[1 6, 9 10 13 81]其中每个子集大2和相等。

Answer 1

您可以使用分而治之的方法。首先，使用median-of-medians算法找到(k-1)/2 th divider。接下来，使用选定的元素将列表分成两个子列表。在每个子列表上重复该算法以查找其余分隔符。

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