algorithm - 从数组中找到领导者

Question

领导者是出现多于数组元素一半的数字。如果数组中的两个连续部分具有该领导者（即领导者出现在该部分中其他元素的一半以上），则将定义 Equi-leader respective。由于部分可能会有所不同，因此阵列可以有多个 Equi-leader。说，我找到了一个数组的领导者 x，现在我想找到平等领导者的数量。

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

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

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

标签： algorithm

Answer 1

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

设数组的长度为 N。假设第一部分（子部分）的长度为 L，因此第二部分的长度为 NL。令 C ₁为第一部分中值 X 的数量，而 C ₂为第二部分中值 X 的数量。

根据 equi-leader 的定义（希望我猜对了），我们有 C ₁ > L / 2 和 C ₂ > (NL) / 2。将它们加在一起，我们有 C ₁ + C ₂ > N/2。

因此，任何平等的领导者也是整个阵列的领导者。由于最多可以有一个领导者，所有平等领导者都必然等于这个领导者。