支持類隊列操作和模式查找的數據結構

這是一個接近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）。 –

支持類隊列操作和模式查找的數據結構

回答

相關問題