这是大约 3 年前问我的一个面试问题，我在不久前就在思考这个问题。
设计一个支持以下操作的数据结构：insert_back()、remove_front() 和 find_mode()。所需的最佳复杂性。
我能想到的最佳解决方案是 O(logn) 用于插入和删除，O(1) 用于模式。这就是我解决它的方法：保留一个队列 DS 来处理插入和删除的元素。还要保留一个最大堆排序的数组和一个哈希表。哈希表包含一个整数键和指向该元素的堆数组位置的索引。堆数组包含一个有序对 (count,element)，并在 count 属性上排序。
插入：将元素插入队列。从哈希表中找到堆数组索引的位置。如果不存在，则将元素添加到堆中并向上堆。然后将最终位置添加到哈希表中。增加该位置的计数并根据需要向上或向下堆化以恢复堆属性。
删除：从队列头部删除元素。从哈希表中，找到堆数组索引中的位置。减少堆中的计数并根据需要向上或向下重新堆以恢复堆属性。
查找模式：数组堆头部的元素 (getMax()) 将为我们提供模式。
有人可以建议更好的东西。我能想到的唯一优化是使用斐波那契堆，但我不确定这是否适合这个问题。
O(1)我认为所有操作都有一个解决方案。
你需要一个双端队列和两个哈希表。
第一个是一个链接的哈希表，其中每个element存储它的count，next按计数顺序的previous元素和按计数顺序的元素。然后，您可以在恒定时间内查看该哈希表中下一个和上一个元素的条目。对于此哈希表，您还保留和更新计数最多的元素。( element -> count, next_element, previous_element)
在每个不同数量的元素的第二个哈希表中，您将具有该计数的元素存储在第一个哈希表的范围的开头和结尾。请注意，此哈希表的大小将小于n（O(sqrt(n))我认为是 ）。( count -> (first_element, last_element))
基本上，当您在双端队列中添加或删除元素时，您可以通过分析其next和previous元素来找到它在第一个哈希表中的新位置，以及在恒定时间内在第二个哈希表中计数的旧值和新值。您可以使用链表算法在恒定时间内删除和添加第一个哈希表中的元素。您还可以在恒定时间内更新第二个哈希表和具有最大计数的元素。
如果需要，我会尝试编写伪代码，但对于许多特殊情况，它似乎相当复杂。