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

Question

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

18

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

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

为了方便起见，下面简述一下问题陈述。

给定长度小于等于2,000,000的整数数组，其中元素取值范围在[0,1,000,000]之间，找到一个最长子数组，该子数组包含占数组长度超过一半的主要元素。

主要元素被定义为在长度为n的列表中出现次数大于 floor(n/2) 次的元素。

时间限制: 1.5秒

例如:

如果给出数组是[1,2,1,2,3,2],

答案是5，因为从位置1到5（0-索引）的长度为5的子数组[2,1,2,3,2]具有数字2，它出现了3次，大于floor(5/2)。请注意，我们不能取整个数组，因为3 = floor(6/2)。

我的尝试:

首先想到的是一种明显的暴力（但正确）解决方法，它固定子数组的起始和结束索引，并循环检查是否包含主要元素。然后取包含主要元素的最长子数组的长度。这个算法的时间复杂度为O(n^2)，但可以通过一些小优化。显然，这种方法无法通过时间限制。

我还想将元素划分到包含其索引的排序顺序的桶中。

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

1: 0, 2

2: 1, 3, 5

3: 4

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

请问有人能向我提供更好的解决此问题的方法吗？

编辑：

感谢PhamTrung和hk6279的回答，我解决了这个问题。虽然我接受了PhamTrung的答案，因为他首先提出了这个想法，但我强烈建议查看hk6279的答案，因为他的答案详细阐述了PhamTrung的想法（还附带了漂亮的正式证明！）。

- Donald

将索引分成桶是一个好主意，可以实现O(N)算法。 - Matt Timmermans

@Matt Timmermans 怎么做？ - Donald

是的...这是一个复杂的答案，我现在没有时间写，但是给你一个提示：从索引列表中，您可以计算出每个索引之前匹配元素的累积计数列表。从该列表中的两个相邻元素，您可以轻松地计算出所有中间索引处的累积匹配-不匹配。对于每个索引，以大多数匹配元素结尾的最长子数组始于具有较小累积匹配-不匹配计数的最小索引。 - Matt Timmermans

@MattTimmermans，你上面的评论很有道理 - “对于每个索引，以该索引结尾的最长子数组，其大多数匹配元素从具有较小的累积匹配-不匹配计数的最小索引开始。”（我认为Pham Trung的答案也是这样建议的。）然而，为了使整个算法O(n)，正如你所说，似乎我们需要在O(1)中找到最小的索引。你有什么想法来实现它？ - גלעד ברקן

随着索引列表的进展，您跟踪匹配-不匹配值。当遇到低于所有先前值的值时，请将其与索引添加到列表末尾。列表中的值将单调递减。当您不添加新值时，您正在查找列表中的当前值。您可以进行二进制搜索，但由于您正在寻找的值变化非常缓慢，因此更快的方法是在列表中向上或向下移动以跟踪所需位置的更改。每个列表项的摊销时间为O（1）。 - Matt Timmermans

@MattTimmermans 啊，对了。对于任何向上出现的 k 次，在 O(1) 中回溯列表时，如果我们跳下来，我们最多可以添加 k 次迭代，回溯列表向下。因此，似乎每个字符总共会受到约 2 * num_occurences 的限制。不错。（在我的答案中，我建议在向上时进行哈希处理，但是您的建议在实践中可能更快。） - גלעד ברקן

4个回答

2

本文详细解释并说明了@PhamTrung的解决方案中第2次尝试是如何工作的。

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

找到有效数组中大多数元素的最大数量，表示为m
- 这是通过@PhamTrung解决方案中的第2次尝试完成的
返回min( 2*m-1, 给定数组的长度)

概念

这个尝试源于解决最长正子数组的方法

我们维护一个计数器数组，用于每个唯一数字x。当我们遇到x时，将其加1。否则，减去1。

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

当存在两个计数器的值满足右侧计数器的值大于或等于左侧计数器的值时，我们可以从被盲目忽略的计数器数组中获取有效数组。请参见证明部分。

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

我们可以通过不记录大于其前一个有效计数器的计数器来进一步改进它。以索引8、9的计数器为例，如果您可以使用索引9形成子数组，则必须能够使用索引8形成子数组。因此，我们只需要用于计算的[1（0），0（3），-1（8）]。

您可以使用计数器数组上的二进制搜索来使用当前计数器值与所有先前计数器值形成有效子数组的当前索引（如果找到最接近的小于或等于当前计数器值的值）

证明

对于特定的x，当右计数器比左计数器大r时，其中k，r>=0，必须存在k+r个x和k个非x的数字存在于左计数器之后。因此

两个计数器的位置分别为索引位置i和r+2k+i
在[i，r+2k+i]之间形成的子数组恰好有k+r+1个x
子数组长度为2k+r+1
子数组有效当(2k+r+1) <= 2 * (k+r+1) -1

过程

让m=1
从左到右循环数组
对于每个索引p_i
- 如果是第一次遇到这个数字，
  1. 创建一个新的计数器数组[1(p_i)]
  2. 创建一个新的索引记录存储当前索引值（p_i）和计数器值（1）
- 否则，重复使用数字的计数器数组和索引数组，并执行
  1. 通过c_prev+2-(p_i - p_prev)计算当前计数器值c_i，其中c_prev，p_prev是索引记录中的计数器值和索引值
  2. 执行二进制搜索，找到可以使用当前索引位置和所有先前索引位置形成的最长子数组。 即在计数器数组中查找最接近c_i的c，c_closest。如果找不到，请转到步骤5
  3. 计算子数组中的x数量
    
    r = c_i - c_closest
    
    k = (p_i-p_closest-r)/2
    
    x的数量=k+r+1
  4. 如果子数组具有x的数量>m，则更新计数器m
  5. 如果计数器值小于上次记录的计数器值，则通过附加当前计数器来更新计数器数组
  6. 通过当前索引（p_i）和计数器值（c_i）更新索引记录

- hk6279

如果我们忽略 #，我们该如何解决这个问题：[3, 3, 1]？使用您的算法，我们只会看到 [3, 3] 对吗？ - Donald

我的错。我刚才看到了标题“在有效数组中找到大多数元素的最大数量...”。在这种情况下，您的方法是正确的。非常感谢您详细的解释！我会尝试一下。如果我没错的话，您的方法具有O(nlogn)的时间复杂度。是否有任何技巧可以使其成为O(n)？ - Donald

@LanceHAOH 这个算法与PhamTrung的第二次尝试完全相同，因此它将具有O(nlogn)的时间复杂度和O(n)的空间复杂度。有什么技巧可以使其变为O(n)吗？我无法想到任何方法来消除二分搜索以减少时间。 - hk6279

1

非常感谢您花费这么多时间来帮助我！我实施了这个解决方案并获得了AC! 但是由于PhamTrung首先提出了这个想法，我将标记他的答案为已接受，但我将在我的编辑问题帖子中同时提及您们俩的答案作为推荐答案。 - Donald

（如果你感兴趣的话，我想我的答案中可能会有一个“使其O(n)的技巧”。） - גלעד ברקן

0

为了完整起见，这里是一个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              *

对于上述总和序列的最小值，关于 c 的图形可能如下：

  min_sum

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

显然，对于每个c的出现，我们正在寻找sum_sequence小于或等于当前sum_sequence的最左边的c的出现。非负差异意味着c是多数派，并且最左边保证了该区间在我们的位置上是最长的。（我们可以从c的内部边界推断出一个最大长度，该长度由除c以外的字符限制，因为前者可以灵活变化而不影响多数派。）

观察到从一个c的出现到下一个c的出现，它的sum_sequence可以减少任意大小。但是，在两个连续的c的出现之间，它只能增加1。我们可以记录线性段，由c的出现标记。以下是一个视觉示例：

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

我们遍历 c 的出现次数，并维护指向 min_sum 最优段的指针。显然，我们可以从前一个值中推导出下一个 c 的 sum_sequence 值，因为它恰好减少了之间字符的数量。

c 的 sum_sequence 增加对应着最优 min_sum 段的指针向后移动 1 或不变。如果指针没有改变，我们将当前的 sum_sequence 值哈希为当前指针值的键。可能会有 O(num_occurrences_of_c) 个这样的哈希键。

对于 c 的任意减少的 sum_sequence 值，要么 (1) sum_sequence 低于记录的最低 min_sum 段，因此我们添加一个新的、更低的段并更新指针，要么 (2) 我们之前已经看到过这个确切的 sum_sequence 值（因为所有增加都只是 1），可以使用哈希在 O(1) 时间内检索到最优的 min_sum 段。

正如Matt Timmermans在問題評論中指出的那樣，如果我們只是通過迭代列表來不斷更新最優min_sum指針，我們仍然每個字符出現只執行O(1)攤銷時間迭代。我們看到對於每個增加的sum_sequence段，我們可以在O(1)中更新指針。如果我們僅對下降進行二分搜索，則對於每個k次出現，我們最多會添加(log k)次迭代（假設我們一直跳下去），這使我們的整體時間保持在O(n)。

- גלעד ברקן

-1

算法：基本上，Boyer-Moore算法是在寻找一个后缀sufsuf，其中suf[0]suf[0]是该后缀中的大多数元素。为了做到这一点，我们维护一个计数器，每当我们看到当前候选的大多数元素的实例时，计数器就会增加，而每当我们看到其他任何东西时，计数器就会减少。每当计数器等于0时，我们就会有效地忘记nums中当前索引之前的所有内容，并将当前数字视为大多数元素的候选者。不立即明显的是，为什么我们可以忘记nums的前缀-考虑以下示例（插入管道以分隔非零计数的运行）。

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

在这里，索引0处的7被选为第一个大多数元素的候选者。计数器最终会在处理索引5之后达到0，因此索引6处的5将成为下一个候选者。在这种情况下，7是真正的大多数元素，因此通过忽略此前缀，我们正在忽略相等数量的大多数和少数元素-因此，7仍将是通过丢弃第一个前缀形成的后缀中的大多数元素。

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 5, 5, 5, 5]

现在，多数元素是5（我们将数组的最后一组从7改为了5），但我们的第一个候选人仍然是7。在这种情况下，我们的候选人不是真正的多数元素，但我们仍然不能丢弃比少数元素更多的多数元素（这将意味着在重新分配候选人之前计数可能会达到-1，这显然是错误的）。

因此，鉴于在两种情况下都不可能丢弃比少数元素更多的多数元素，我们可以安全地丢弃前缀，并尝试递归解决后缀的多数元素问题。最终，将找到一个后缀，其中计数不会达到0，并且该后缀的多数元素必定与整个数组的多数元素相同。

以下是Java解决方案：

时间复杂度：O(n)

空间复杂度：O(1)

public int majorityElement(int[] nums) {
    int count = 0;
    Integer candidate = null;

    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        count += (num == candidate) ? 1 : -1;
    }

    return candidate;
}

- Neha

3

这是为了找到“majorityElement”，而不是回答这个问题。 - Pham Trung

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pham Trung · Accepted Answer

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

尝试1：答案相当复杂，所以我将讨论一个简短的想法。

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

从左到右处理数字x的每个出现，在索引i处，让我们添加一个段(i，i)表示当前子数组的开始和结束。之后，我们需要查看该段左侧，并尝试将该段的左邻居合并到(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的出现，-1表示否则；问题可以转换为找到和为正的子数组）

因此，在二进制搜索的帮助下，上述算法仍具有O(n ^ 2 log n)的复杂度（如果我们有n/2个唯一的数字，则需要n/2次执行上述过程，每次需要O(n log n)）。

为了改进它，我们做出了一个观察，实际上我们不需要存储所有计数器的所有值，而只需要存储x的计数器值，我们看到我们可以存储上面数组计数器的值：[1，#，＃，0，1，＃，＃，＃，-1，0]

这将导致O(n log n)的解决方案，只需一次遍历每个元素。