將哈希錶轉換爲O（log（k）* k + n）中的排序數組

Question

因此，在我的數據結構講座中，我被告知可以使用k個鍵和n個元素將哈希錶轉換爲已分攤數組O（log（k）* k + n）。但是，它背後沒有任何理由。我發現它有點混亂，爲什麼我試圖找到一個算法來做到這一點。

我不能拿出一個。我想這應該是一個衆所周知的，因爲我們只是沒有證據就注意到它，但我找不到它。你知道這個問題的解決方案嗎？

Answer 1

如果您的意思是按鍵排序，那麼k * log（k）對鍵和n進行排序，以便根據排序後的鍵插入元素。因此O（klog（k）+ n）。該算法是：

1. 排序鍵（可能是一個新的數組）
2. 爲n個元素的排序完畢關鍵字數組在創建房間空數組
3. 迭代並插入所有元素的每個關鍵在新陣列中

步驟1取O（klog（k））個操作，步驟3取O（n）。