支持类队列操作和模式查找的数据结构

这是一个接近3年前问我的面试问题，我一直在思考这个问题。支持类队列操作和模式查找的数据结构

设计一个支持以下操作的数据结构： insert_back（），remove_front（）和find_mode（）。最佳复杂度需要。

我能想到的最佳解决方案是插入和删除的O（logn）和模式的O（1）。这就是我解决它的方法：保留一个队列DS来处理插入和删除哪个元素。还保留一个数组，这是最大的堆排序和哈希表。哈希表包含一个整数键和一个索引到该元素的堆数组位置。堆数组包含有序对（count，element），并在count属性上进行排序。

插入：插入元素到队列中。从散列表中查找堆阵列索引的位置。如果不存在，则将该元素添加到堆并向上堆积。然后将最终位置添加到散列表中。增加该位置的计数并根据需要向上或向下堆积以恢复堆属性。

删除：从队列头部删除元素。在哈希表中，在堆数组索引中找到一个位置。减少堆中的计数并根据需要向上或向下重新上移以恢复堆属性。

查找模式：数组堆的头部的元素（getMax（））会给我们模式。

有人可以提出更好的建议。我能想到的唯一优化是使用Fibonacci堆，但我不确定这是否适合这个问题。

来源

2013-09-27 rajaditya_m

你所描述的是一个'Deque'，它非常标准。 – MoonKnight

但是，deque（我认为这是一个双端队列）如何跟踪数组中发生最大次数的元素？任何链接将有所帮助。感谢您的及时答复 –

啊，我很抱歉。我忽略了需求的'Find_Mode'方面。我应该说你描述的结构是['Deque']（http://en.wikipedia.org/wiki/Double-ended_queue#Complexity）。您可以看到，基本实现中的所有操作都是O（1） - 但是，find不是其中之一......很遗憾，您可以在这里浪费时间。 – MoonKnight

我认为所有操作都有一个解决方案O(1)。

你需要一个deque和两个哈希表。

第一个是链接的哈希表，其中每个element您存储其count，在计数顺序next元素和计数顺序previous元素。然后，您可以在恒定时间内查看该哈希表中的下一个和上一个元素的条目。对于这个散列表，您还保留并更新了最大计数的元素。（element -> count, next_element, previous_element）

在每个不同数量的元素的第二个散列表中，您将具有该数量的元素存储在第一个散列表的范围的开始和结束位置。请注意，这个散列表的大小将小于n（我认为它是O(sqrt(n))）。（count -> (first_element, last_element)）

基本上，当添加元素或从双端队列中删除一个元素，则可以通过分析其next和previous元素找到在第一散列表中的新位置，并为新老和计数的值在第二个哈希表中定时。您可以使用链接列表的算法在常量时间内移除并添加第一个哈希表中的元素。您也可以在常量时间内更新第二个散列表和最大数量的元素。

我会尝试编写伪代码，如果需要，但它似乎是相当复杂的许多特殊情况。

来源

2013-09-27 16:02:16 Kolmar

我同意这个答案，因为这是我向我的面试官提出的一个，它更自然。你也说过同样的事情，我的面试官也说过这样的话：“这是很难编码的，并且可能会出现一些不适用的角落案例。”因此，我认为这样做更容易实现，尽管解决方案较慢。 –

我认为它在任何情况下都可以工作，但是，是的，编写代码可能非常棘手，因此应该对其进行非常彻底的测试。 – Kolmar

我不明白：值多次出现时，它会在第一个哈希表中出现一次还是多次？我会多次思考，因为对于不同的副本，next和previous是不同的，但是当添加一个新副本时，你必须更新所有副本的计数，这可能是O（N）。 –

支持类队列操作和模式查找的数据结构

回答

相关问题