查找包含多数元素的最长子数组

Question

我正在尝试解决这个算法问题：

https://dunjudge.me/analysis/problems/469/

为了方便起见，我总结了下面的问题陈述。

给定一个长度为 （

多数元素定义为发生的元素

时限：1.5s

例如:

如果给定的数组是[1，2，1，2，3，2]，

答案是5，因为从位置1到5 (0索引)的长度为5的子数组[2，1，2，3，2]具有出现为3的数字2

首先想到的是一个明显的强力(但正确)解决方案，它修复子数组的开始和结束索引，并遍历它以检查它是否包含多数元素。然后我们取包含多数元素的最长子阵列的长度。这在O(n^2工作)与一个小的优化。显然，这不会超过时间限制。

我还在考虑将元素划分为按排序顺序包含其索引的存储桶。

使用上面的例子，这些桶将是:

1: 0, 2

2: 1, 3, 5

3: 4

然后，对于每个存储桶，我将尝试将索引合并在一起，以找到包含 k 作为多数元素的最长子数组，其中 k 是该存储桶的整数标签。然后，我们可以取 k 的所有值的最大长度。我没有尝试这个解决方案，因为我不知道如何执行合并步骤。

编辑：

感谢PhamTrung和hk6279的回答，我解决了这个问题。虽然我接受了PhamTrung的回答，因为他首先提出了这个想法，但我强烈建议看看hk6279的回答，因为他的回答阐述了PhamTrung的想法，而且更加详细(还提供了很好的正式证明！).

Answer 1

为了完整起见，这里有一个O（n）理论的大纲。考虑以下内容，其中*是与c不同的字符：

    * c * * c * * c c c
 i: 0 1 2 3 4 5 6 7 8 9

对于 c 加 1 和对 c 以外的字符减去 1 的图可能如下所示：

  sum_sequence

  0    c               c
 -1  *   *   c       c
 -2        *   *   c
 -3              *

对于< code>c，上述求和序列的最小值的图形如下所示:

  min_sum

  0    c * *
 -1  *       c * *
 -2                c c c

显然，对于每次出现 c，我们正在寻找最左边出现的 c，sum_sequence小于或等于当前sum_sequence。非负差值意味着 c 占多数，最左边的保证区间是我们位置的最长区间。（我们可以从 c 的内部边界推断出由 c 以外的字符限定的最大长度，因为前者可以灵活而不影响多数。

请注意，从 c 的一个出现到下一个，其sum_sequence可以减小任意大小。但是，它只能在两次连续出现的 c 之间增加 1。我们可以记录线性段，而不是 c 的每个值 min_sum，由 c s 出现标记。一个视觉示例：

[start_min
    \
     \
      \
       \
      end_min, start_min
                  \
                   \
                   end_min]

我们遍历出现的c并维护一个指向min_sum最佳段的指针。显然，我们可以从前一个值导出c的下一个sum_sequence值，因为它正好被中间的字符数所减少。

c的sum_sequence的增加对应于1向后移动或指向最佳min_sum段的指针没有变化。如果指针没有变化，我们散列当前sum_sequence值作为当前指针值的键。可以有O（num_occurrences_of_c）这样的散列键。

随着c的sum_sequence值的任意减少，（1） 低于记录的最低 段，因此我们添加一个新的较低段并更新指针，或者（2）我们之前已经看到了这个精确的 sum_sequence值（因为所有增加都是 1only），并且可以使用我们的哈希来检索 中的最佳

正如Matt Timmermans在问题评论中指出的那样，如果我们只是通过在列表上html" target="_blank">迭代来不断更新指向最佳min_sum的指针，我们仍然只会在每个字符出现时执行O（1）摊销时间迭代。我们看到，对于sum_sequence的每一个递增段，我们都可以更新O（1）中的指针。如果我们只对下降使用二进制搜索，我们最多会为每一次k出现添加（logk）迭代（这假设我们一直向下跳），这将使我们的总时间保持在 。

Answer 2

这详细说明并解释了@PhamTrung解决方案中的尝试 2 是如何工作的

获取最长子数组的长度。我们应该

• 求有效数组中多数元素的最大数量，表示为 m
  • 这是通过@PhamTrung解决方案中的尝试 2 完成
  的

  概念

  这一尝试源于一种求解最长正子阵列的方法

  我们为每个唯一的数字x维护一个计数器数组。当我们遇到x时，我们会执行1。否则，请执行-1。

  以数组[0,1,2,0,0,3,4,5,0,0,1,0]和唯一编号0为例，我们有数组计数器[1,0，-1,0,1,1,0,1，-1，-2，-1,0，-1，0]。如果我们盲掉那些不是目标唯一数的，我们得到[1，#，#，0,1，#、#，#、-1,0，#，0]。

  当存在两个计数器时，我们可以从盲计数器数组中获取有效数组，使得右侧计数器的值大于或等于左侧计数器的值。请参阅校样部分。

  为了进一步改进它，我们可以忽略所有的#，因为它们是无用的，我们得到了计数（索引）格式的[1（0），0（3），1（4），-1（8），0。

  我们可以通过不记录大于其先前有效计数器的计数器来进一步改进这一点。以指数8，9的计数器为例，如果你能用指数9构成子阵列，那么你一定能用指数8构成子阵列。所以，我们只需要[1(0)，0(3)，-1(8)]进行计算。

  通过在计数器数组上查找小于或等于当前计数器值的最接近值(如果找到的话)，可以使用当前索引和所有以前的索引形成有效的子数组

  证据

  对于特定的x，当右计数器比左计数器大< code>r时，其中k，r

  1. 两个计数器位于索引位置 i 和 r 2k i
  2. [i， r 2k i] 之间的子数组形式正好有 k r 1 个 x
  3. 子阵列长度为 2k r 1
  4. 子数组的有效为 （2k r 1）

  程序

  • 让m=1
  • 从左到右循环数组
  • 对于每个索引p_i
    • 如果号码是第一次遇到， <块引用>
      1. 创建一个新的计数器数组[1（p_i）]
      2. 创建一个新的索引记录，存储当前索引值（p_i）和计数器值（1）

    >

  • 计算当前计数器值 c i 由 c prev 2-（p_i - p prev），其中 c prev，p _prev 是索引记录中的计数器值和索引值
  • 执行二叉搜索以查找可以用当前索引位置和所有先前索引位置形成的最长子数组。 即在计数器数组中找到最近的 c，c_最接近，其中 c

    r=c_i-c_最接近

    k=（p_i-p_最接近-r）/2

    x 的数目 = k r 1

Answer 3

注意：尝试 1 是错误的，因为@hk6279给出了一个反例。感谢您指出。

尝试1：答案很复杂，所以我将讨论一个简单的想法

让我们逐一处理每个唯一的数字。

在索引i处，从左到右处理每次出现的数字x，让我们添加一个段 ，指示当前子阵列的开始和结束。之后，我们需要查看该段的左侧，并尝试将该段的左邻居合并为 （i，i），（因此，如果左侧是 （st，ed），如果满足条件，我们会尝试将其合并为 （st，i）），并继续合并它们，直到我们无法合并，或者没有左邻居。

我们将所有这些段保存在一个堆栈中，以便更快地查找/添加/删除。

最后，对于每个片段，我们尝试尽可能地放大它们，并保持最大的结果。

时间复杂度应为O（n），因为每个元素只能合并一次。

尝试 2：

让我们逐一处理每个唯一的数字

对于每个唯一的数字x，我们维护一个计数器数组。从0到数组末尾，如果我们遇到值x，我们会增加计数，如果我们没有，我们会减少计数，所以对于这个数组[0,1,2,0,0,3,4,5,0,0]和数字0，我们有这个数组计数器

[1,0,-1,0,1,0,-1,-2,-1,0]

因此，为了生成以特定索引i结束的有效子阵列，counter[i]-counter[start-1]的值必须大于0（如果您将数组视为由1和-1项组成，则很容易解释这一点；如果使用1，则表示出现x，否则为；问题可以转化为查找和为正数的子数组）

所以，在二进制搜索的帮助下，上述算法仍然有O（n^2 log n）的复杂度（如果我们有n/2个唯一数字，我们需要做上述过程n/2次，每次取O（n log n））

为了改进它，我们观察到，我们实际上不需要存储所有计数器的所有值，而只需要存储< code>x的计数器的值，我们看到我们可以存储上述数组计数器的值:

[1,#,#,0,1,#,#,#,-1,0]

这将导致O（n log n）解决方案，它只遍历每个元素一次。