我有一個未排序陣列大小Ñ的和我需要找到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和相等。
你能舉一個例子嗎? –
@ A.Shoob對你很好。現在,請刪除您的意見,說同樣的事情。這將有助於減少總評論的數量。 (我也會刪除我的) – mickmackusa