algorithm - 从数组中找到领导者

Question

领导者是出现次数超过数组元素一半的数字。如果数组中的两个连续部分具有该领导者(即领导者出现在 respective 部分中其他元素的一半以上)，则将定义 Equi-leader。由于截面可能不同，阵列可以有多个 Equi-leader。比方说，我找到了一个数组的首领 x，现在我想找到同等首领的数量。

如果一个部分和连续的部分 x 出现的次数多于其他元素(x > non_X 对于段)，是否意味着在这 2 个段中 x 出现的次数也超过了其他元素的一半？请记住，x_Total > Array_Length/2

一个部分是一个子数组，比如说，取 S 索引中的元素。这会创建 [0,1,....., S] 和 [S+1, S+2, .] 的 2 个连续子数组。 .... N-1] 我们需要两个部门的领导者。

我知道这是真的，但是，如何证明呢？不寻找代码实现。

Answer 1

仍然不确定我是否理解这个问题，但无论如何。

设数组的长度为N。假设第一部分(小节)的长度为 L，因此第二部分的长度为 N-L。设C₁为第一部分中值X的个数，C₂为第二部分中值X的个数。

根据 equi-leader 的定义(希望我没记错)，我们有 C₁> L/2 和 C₂> (N-L)/2。将它们加在一起，我们有 C₁ + C₂> N/2。

因此，任何 equi-leader 也是整个阵列的领导者。由于最多只能有一个领导者，因此所有等领导者都必然等于这个领导者。