algorithm - 一种有效的重命名算法

Question

如果我有一个变量列表，[a，b，a，c，a，a，d，b，c，d，a] 顺序很重要，我必须将它们重命名为整数，那么最好的算法是什么我可以使用吗？

一个简单的算法将是：

1. 创建一个空的哈希表，HT。
2. 对于列表中的每个变量，
   1. 如果它没有被索引，则为其分配一个新的索引并将（变量，索引）放入HT中。
   2. 如果它被索引，则使用索引。

在上述情况下，解决方案将是 [1, 2, 1, 3, 1, 1, 4, 2, 3, 4, 1]

我关心“n”哈希查找以及随之而来的复杂性。对于非常长的列表（具有更多不同的变量），性能可能非常糟糕。有没有人有更好的算法来处理这个问题？

请注意，虽然该示例使用 ascii 字符，但列表的元素可以是任意字符串，列表的长度可以是任意长（> 100k）等。

Answer 1

O(n)最坏情况的哈希查找仅在使用简单的冲突解决方案时发生（并且所有项目都映射到相同的哈希值） - 您实际上使用哈希，因为您希望冲突是“罕见的”，因此平均受益于O(1)查找时间。

因为您必须检查所有变量是否有重复项，所以您的表现不会比O(n)总体好。

也许您可以利用其他信息 - 变量名的第一个实例列表是否已排序？如果是，您只需要存储到目前为止遇到的按字典顺序排列的最大变量名 ( vmax)，null并在列表元素出现时将其与它们进行比较。如果被测元素vcur小于或等于vmax，您之前已经看过变量名，否则增加一个计数器，与之关联vcur并设置vmax为vcur。