与数组具有相同"度"的子数组的数量

Question

因此在测验中询问了这个问题,问题如下:

您将获得一个数组'a',其元素范围为1-10 ⁶ ,数组大小可能最大为10 ⁵现在我们要求找到与原始数组具有相同"degree"的子数组.数组的度数定义为数组中最大出现元素的频率.多个元素可以具有相同的频率.

我被困在这个问题上一个小时但却想不到任何解决方案.我该如何解决？

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]

您有三种模态 (1 2 5)，阶数为 3。索引范围为

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 个以上的子数组。

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