2017-04-08 95 views
0

我有一個未排序陣列大小Ñ的和我需要找到k-1個除數所以每子集是相同的尺寸(如數組進行排序之後) 。陣列大小n爲k相同尺寸組

我看過這個問題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和相等。

+1

你能舉一個例子嗎? –

+0

@ A.Shoob對你很好。現在,請刪除您的意見,說同樣的事情。這將有助於減少總評論的數量。 (我也會刪除我的) – mickmackusa

回答

0

您可以使用分而治之的方法。首先,使用median-of-medians算法找到(k-1)/2 th divider。接下來,使用選定的元素將列表分成兩個子列表。在每個子列表上重複該算法以查找其餘分隔符。

最大遞歸深度爲O(log k),每個級別的所有子列表的總成本爲O(n),所以這是一個O(n log k)算法。

+0

非常感謝。 –