c++ - 在具有重复项的一长串数据的滚动窗口中查找模式

Question

给出一个数据序列(有重复项)，沿着数据序列移动一个固定大小的窗口，并在每次迭代时在窗口中查找模式，其中最旧的数据被删除，新数据被插入到窗口中。

我在这里找不到更好的解决方案。

我的想法:使用哈希表，key就是数据，key的数据就是数据在窗口中出现的频率。

第一次迭代时，遍历窗口中的每条数据并放入hashtable，同时计算每条数据出现的频率。之后遍历哈希表，返回出现频率最高的数据。对于接下来的每次迭代，搜索哈希表中最旧的数据，如果它在 hahstable 中，则将其频率减 1，如果它变为 0，则使用新数据替换旧数据。否则，只需将新数据插入 hahstable 即可。遍历表并返回模式。

它是 O(n * m)，其中 n 是数据序列大小，m 是窗口大小。缺点是:散列表的大小不固定，可能会有调整大小的开销。每次迭代都要遍历表，效率不高。

可以用 O(n lg m) 或 O(n) 来完成吗？

感谢任何帮助。

谢谢

另一种解决方案:在第一次迭代中，建立一个哈希表，其中数据作为键，其频率作为与键关联的值。在哈希表的基础上，构建一个以频率为键、关联数据为值的多重图。

之后，在每次迭代中，在窗口中，删除最旧的数据并更新哈希表，然后用哈希表中最新更新的数据更新 multimap。如果map key有多个数据，只用频率不变的数据替换新的。但是，添加具有新频率和数据的新对。

在窗口中，获取新数据并更新哈希表，用哈希表中最新更新的数据更新 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 pointer} 对。
• 一个优先队列持有 M 个计数。

及时更新O(lg M):

• 在环形缓冲区中找到离开值O(1),
• 在二叉搜索树中找到相同的值O(lg M),
• 调整链接的 PQ 节点中的计数。
  • 在该节点上调整优先级 O(lg M)
• 用新的替换旧的环形缓冲区条目 O(1)
• 在二叉搜索树中找到新值 O(lg M),
• 调整链接的 PQ 节点中的计数。
  • 在该节点上调整优先级 O(lg M)
• GetFirst 在 PQ 上找到模式 O(1)

您可以通过添加指向 BST 结构的 nextItem 指针来摆脱环形缓冲区，并保留指向最旧项目的外部指针。这通过一次 BST 查找加快了它的速度，如果值大小大于指针大小，则可能是一个空间胜利。但是该算法的编码变得更加复杂。