---

算法的基本设计思想

本算法旨在寻找一个整数序列中的主元素，即出现次数超过序列长度一半的元素。核心思想是利用**"抵消法"**（或称为候选法、摩尔投票算法 Moore's Voting Algorithm）。

具体步骤如下：

1. 第一阶段：寻找候选主元素。

   • 初始化两个变量：candidate（候选元素）和 count（计数器）。
   • 遍历整个序列。
   • 如果 count 为 0，则将当前元素设为 candidate，并将 count 设为 1。
   • 如果当前元素与 candidate 相同，则 count 加 1。
   • 如果当前元素与 candidate 不同，则 count 减 1。
   • 核心思想： 如果一个元素是主元素，那么它的出现次数必然超过总数的一半。当它遇到另一个不同的元素时，它们可以“抵消”一次。主元素由于数量优势，在所有抵消完成后仍然能保持 count 为正值，并最终成为 candidate。即使不是主元素，也可能在遍历结束时成为 candidate，但其 count 最终会归零或一个较小的值。

2. 第二阶段：验证候选主元素。

   • 在第一阶段结束后，我们得到了一个 candidate。但是，这个 candidate 并不一定是主元素。例如，序列 [1, 2, 3]，1 可能是 candidate，但它不是主元素。
   • 因此，需要再次遍历整个序列，统计 candidate 元素的实际出现次数 actualCount。
   • 如果 actualCount 大于序列长度 n 的一半（即 n / 2），则 candidate 确实是主元素。
   • 否则，序列中不存在主元素。

算法优势： 这种方法只需常数级别的额外空间（用于存储&...