arrays - 与数组相同的 'degree' 子数组的个数

Question

所以这个问题是在测验中提出的，问题是这样的:

给定一个数组 'a'，其元素范围为 1-10⁶ 并且数组的大小最大为 10⁵ 现在我们被要求找到与原始数组具有相同“度数”的子数组数。数组的度定义为数组中最大出现元素的频率。多个元素可以具有相同的频率。

我被这个问题困了将近一个小时，但想不出任何解决方案。我该如何解决？

示例输入:

first-input
1,2,2,3,1
first-output 2
second-input
1,1,2,1,2,2
second-output 4

Answer 1

出现频率最高的元素称为模式；此问题将度数 定义为频率计数。你的任务是:

确定所有模式值。对于每个模式值，找到该值的索引范围。例如，在数组中

[1, 1, 2, 1, 3, 3, 2, 4, 2, 4, 5, 5, 5]

你有阶数为 3 的三种模式 (1 2 5)。索引范围是

1 - 0:3
2 - 2:8
5 - 10:12

您需要计算至少包含这三个范围之一的所有索引范围(子数组)。

我对这个示例进行了调整，使其包含两种基本情况:重叠的模式和不重叠的模式。请注意，包含是一个有争议的问题:如果您有一个数组，其中一种模式的范围包含另一种模式:

[0, 1, 1, 1, 0, 0]

您可以完全忽略外部数组:任何包含 0 的子数组也将包含 1。

分析

子数组由两个数字定义，起始索引和结束索引。由于我们必须有 0 <= start <= end <= len(array)，这就是数组边界之间的“握手”问题。我们有 N(N+1)/2 个可能的子数组。

对于 10**5 个元素，您可以从这里暴力解决问题:对于每对索引，检查该范围是否包含任何模式范围。但是，您可以通过区间识别轻松地减少它。

算法

从左到右步进模式范围。首先，计算包含第一个模式范围 [0:3] 的所有子范围。只有 1 个可能的开始 [0] 和 10 个可能的结束 [3:12]；那是 10 个子数组。

现在移至第二个模式范围 [2:8]。您需要计算包含它的子数组，但排除您已经计算过的子数组。由于存在重叠，您需要一个晚于 0 的起点，或一个在 3 之前的终点。第二个子句在给定范围内是不可能的。

因此，您考虑开始 [1:2]、结束 [8:12]。那是 2 * 5 个子数组。

对于第三个范围 [10:12(无重叠)，您需要一个不包含任何其他子范围的起点。这意味着任何起始点 [3:10] 都可以。由于只有一个可能的端点，因此您有 8*1 个或 8 个以上的子数组。

你能把它变成正式的东西吗？