陣列大小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)算法。