支持基于范围的最常出现的元素查询的数据结构

Question

我正在寻找一种数据结构,我可以在给定的可变范围内找到最常出现的数字(在一组数字中).

让我们考虑以下基于1的数组:

1 2 3 1 1 3 3 3 3 1 1 1 1

如果我查询范围(1,4),数据结构必须重新调整1,这将发生两次.其他几个例子:

(1,13)= 1

(4,9)= 3

(2,2)= 2

(1,3)= 1(所有1,2,3都出现一次,所以返回第一个/最小的一个.此时不那么重要)

我搜索过,但找不到类似的东西.我正在寻找(理想情况下)具有最小空间要求,快速预处理和/或查询复杂性的数据结构.

提前致谢!

Answer 1

您可以创建一个二叉划分树，其中每个节点表示给定范围的 {值 -> 频率} 的直方图，并具有两个子节点，分别表示该范围的上半部分和下半部分。

查询只是递归地将少量这些直方图加在一起以覆盖所需的范围，并扫描一次所得直方图以找到最高出现次数的情况。

有用的优化包括：

• 将直方图相加时，使用频率可变的直方图作为“累加器”
• 一旦达到一定大小（可能小于可能值总数 M 的范围），请停止使用预先计算的直方图，并直接对数字进行计数。我认为这是一种时间/空间的权衡，在很多时候都会得到回报。
• 如果您有固定的少量可能值，请使用数组而不是映射来存储每个节点的频率计数

更新：我对算法复杂性的思考，假设有限的少量可能值 M 和整个范围内总共 N 个值：

• 预处理是O(N log N) - 基本上你需要遍历完整的列表并构建一棵二叉树，为每 M 个元素构建一个节点，以便分摊每个节点的开销
• 查询的时间复杂度为O(M log N) - 基本上将每个大小为 M 的 O(log N) 直方图相加，再加上计算范围两侧的 O(M) 值
• 空间需求为O(N) - 大约。每个大小为 M 的 2N/M 直方图。2 因子是底层 N/M 直方图、下一级 0.5N/M 直方图、第三级 0.25N/M 等的总和...