在滾動窗口中查找包含重複數據的長序列數據的滾動窗口

Question

給出一個數據序列（帶有重複項），沿數據序列移動一個固定大小的窗口，並在每個迭代窗口中查找模式，數據被移除並且新的數據被插入窗口。

我在這裏找不到更好的解決方案。

我的想法： 使用散列表，鍵是數據，鍵的數據是窗口中發生數據的頻率。

在第一次迭代中，迭代窗口中的每個數據並將其放到哈希表中，同時記錄每個數據的頻率。之後，遍歷散列表並返回頻率最高的數據。 對於接下來的每次迭代，搜索散列表中最舊的數據，如果散列表位於hahstable中，則將其頻率降低1，如果它爲0，則使用新數據替換舊數據。否則，只需將新數據插入可移動媒體中即可。遍歷表格並返回模式。

它是O（n * m）其中n是數據序列大小，m是窗口大小。 缺點是：哈希表大小不固定，它可能會調整開銷。每次迭代都必須遍歷表，但效率不高。

可以用O（n lg m）或O（n）來做嗎？

任何幫助表示讚賞。

感謝

另一種解決方案： 在第一次迭代中，建立與數據作爲密鑰和其頻率爲與該鍵關聯值的哈希表。在哈希表的基礎上，建立一個multimap，頻率作爲關鍵字，並將相關數據作爲值。

之後，在每次迭代中，在窗口中，刪除最舊的數據並更新散列表，然後使用散列表中最新更新的數據更新多圖。如果地圖關鍵字有多個數據，請將其替換爲僅有頻率未更改的數據的新數據。但是，添加一個新的頻率和數據對。

在窗口中，獲取新數據並更新散列表，使用散列表中最新更新的一個更新多圖。

位於multimap（二叉搜索樹）最右側的條目是模式，因爲它的值是當前窗口中的最高頻率。

時間O（m + m * lg m + n * lg m）如果n >> m，O（n lg m）。 空間：O（m）

有什麼更好的想法？

Answer 1

空間O（M）：

• 一個環形緩衝器來保存所述M的值。
• 一個BST持有M {value，PQ指針}對。
• 一個優先隊列持有M個計數。

更新在時間O（LG M）：

• 查找在環形緩衝O(1)離開的值，
• 查找在BST O(lg M)相同的值，
• 調整在計數鏈接的PQ節點。
  • 做一個節點上調整優先O(lg M)
• 更換一張新O(1)
• 老環形緩衝區條目查找的BST O(lg M)新值，
• 調整計數鏈接PQ節點。
  • 做一個調整優先級的節點O(lg M)
• GetFirst上PQ上找到模式O(1)

你可以通過添加nextItem指針BST結構擺脫了環形緩衝區，並保持一個外部指針到最舊的項目。這可以通過一次BST查找加速它，並且如果值大小大於指針大小，則可能會贏得空間。但是該算法變得更加複雜。

Answer 2

回顧解決前面的問題...

維護數據值的環形緩衝器。製作一個頻率/數據值對。

保持將數據鍵入到這些對的映射;做一個multimap，鍵入頻率，也包含這樣的對。

在每一步前進通過數據，該模式是在頻率鍵控的地圖上的最後一個條目。可能會有一個關係 - 如何處理這個問題是讀者的一個練習。報告模式後，您需要使用地圖查找屬於要刪除的值的對;然後從多映射中檢索所有具有被刪除值的頻率的條目並找到具有正確值的條目。刪除，修改並重新插入節點到map和multimap中以處理刪除的數據;使用類似的過程來處理添加的數據。根據預期的數據，可能需要首先檢查要插入的值是否與要刪除的值匹配。