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