将哈希表转换为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）。