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

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

令 N 为数组的大小，M 为该数组中不同值的数量。

我正在考虑两个复杂性:预处理和查询大小为 n 的区间，每个都必须是空间和时间的。

---

解决方案 1:

• 空间:O(1) 和 O(M)
• 时间:O(1) 和 O(n + M)

没有预处理，我们查看区间的所有值并找到最频繁的值。

---

解决方案 2:

• 空间:O(M*N) 和 O(1)
• 时间:O(M*N) 和 O(min(n,M))

对于数组的每个位置，我们都有一个累积数组，它为每个值 x 提供 x 在该位置之前的数组中的次数。

给定一个区间，我们只需要将每个 x 减去 2 个值即可找到该区间内 x 的数量。我们遍历每个 x 并找到最大值。如果 n < M，我们迭代区间的每个值，否则我们迭代 x 的所有可能值。

---

解决方案 3:

• 空间:O(N) 和 O(1)
• 时间:O(N) 和 O(min(n,M)*log(n))

对于每个值 x 构建数组中存在 x 的所有位置的二叉堆。堆中的键是位置，但您还存储了该位置与数组开头之间的 x 总数。

给定一个区间，我们只需要每个 x 减去 2 个值来找到该区间内 x 的数量:在 O(log(N)) 中，我们可以要求 x 的堆在开始之前找到两个位置/间隔结束并减去数字。基本上它比直方图需要更少的空间，但现在的查询在 O(log(N)) 中。