c++ - 创建快速字典

Question

对于一项学校任务，我必须创建一个图表并用它做一些事情。在输入中，每个顶点都有一个 ID，它是一个数字 0-999'999'999。由于我无法创建这么长的数组，因此我无法真正将此 ID 用作邻接矩阵中的键。我的第一个解决方案是创建一个单独的 ID，该 ID 是原始 ID 的任意值，并将其存储在某种字典/ map 中，但是当我获得 10'000 条顶点记录时，查找可能会变慢。该算法必须在 O(n^2) 下，我已经有一个 BFS 和一个拓扑排序。在这种情况下最好的解决方案是什么？作为旁注 - 我不能使用已经建立的库(所以我不能使用图形、 map 、 vector 、字符串类等)，但我可以自己编写代码，如果这是最好的选择的话。

Answer 1

你想要的是一个在 O(logn) 时间内进行查找的二叉搜索树，或者一个在 ~O(1) 时间内进行查找的 HashMap ，或者你可以使用数组路由，在这种情况下，数组的大小将是您的 ID 可以拥有的最大值(在您的例子中，10^9)。

正如@amit 告诉您的那样，检查 AVL/红黑树和 HashMap 。在 O(n) 以下的图表中没有更好的查找方法，除非您可以更改图表的拓扑结构以将其转变为“搜索图表”。