在一次面试中,一位面试官问我如何实现网页浏览器的历史记录,但不显示重复项,需要倒序显示从最近访问到第 5 个访问的网站。
我告诉过我们可以使用链表。当用户进入一个网站时,它将根据节点列表进行检查,如果该网站已经存在于列表中,我们将从列表中删除它并将其添加为头部。如果它不在列表中,它将被简单地添加为列表的头部。但他告诉复杂度的顺序是 O(n*n),他问我是否有任何其他数据结构或数据结构的组合可以用来使复杂度的顺序为 O(n)。我当时没有得到任何线索。如果您有任何想法,请告诉我。
最佳答案
如果您使用链表加上带有指向列表项的指针的哈希表,则可以在常数时间内完成。
关于c++ - C++中哪种数据结构适合实现浏览器历史记录?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25733676/