[C算法]003-寻找主元素

均采用 C 语言来编写，版本为 C17，使用其他版本也可以，仅仅停留在算法层面，各大版本几乎区别不大

题目

2013年统考真题

已知一个整数序列 $A=(a_0,a_1,a_2,...,a_{n-1})$ ，其中 $0<=ai<n (0<=i<n)$ 。
若存在 $a_{p_1}=a_{p_2}=...=a_{p_m}=x$ 且 $m>n/2 (0<=pk<n,1<=k<=m)$ ，则称 $x$ 为主元素。
若 $A=(0,5,5,3,5,7,5,5)$ ，则 $5$ 为主元素；
若 $A=(0,5,5,3,5,1,5,7)$ ，则没有主元素；

分析

这个题目是在求 过半数 的众数，那我们就要拿出大名鼎鼎的摩尔投票算法 (Boyer-Moore Voting Algorithm)，它最擅长的就是求 过半数 的众数。

摩尔投票算法

摩尔投票算法（Boyer-Moore Voting Algorithm）是一种用于在 $O(n)$ 时间复杂度和 $O(1)$ 空间复杂度下，从数组中找出众数（出现次数超过数组长度一半的元素）的高效算法。

以下是关于该算法的详细讲解：

核心思想：同归于尽

摩尔投票算法的直观理解是“对拼消耗”。
想象一个战场，不同的数字代表不同的阵营。如果两个不同阵营的人遇到，就同归于尽；如果遇到同阵营的人，就加入队伍。
由于众数的出现次数超过了总数的一半（即 $\displaystyle \text{count} > \frac{n}{2}$ ），那么即使众数与其他所有非众数进行一对一抵消，最后剩下的也一定会是众数。
算法步骤
算法分为两个阶段：
- 第一阶段：寻找候选人（Candidate）
  1. 初始化一个候选人 candidate 为任意值，计数器 count 为 0。
  2. 遍历数组中的每个元素 x：
    - 如果 count == 0，则将当前元素 x 设为 candidate，并将 count 设为 1。
    - 否则，如果 x == candidate，则 count 加 1。
    - 否则（即 x != candidate），则 count 减 1。
- 第二阶段：验证候选人（可选）
由于第一阶段得到的候选人不一定真的是众数（例如数组为 [1, 2, 3] 时，最后剩下的可能是 3，但 3 并不是众数），如果题目不保证一定存在众数，则需要再次遍历数组，统计该候选人的出现次数。如果次数大于 $\displaystyle \frac{n}{2}$ ，则确定为众数。
图解示例

假设数组为：[2, 2, 1, 1, 1, 2, 2]
1. 遇到 2：count=0，设置 candidate=2, count=1
2. 遇到 2：等于候选人，count=2
3. 遇到 1：不等于候选人，count=1（抵消一次）
4. 遇到 1：不等于候选人，count=0（抵消一次）
5. 遇到 1：count=0，设置 candidate=1, count=1
6. 遇到 2：不等于候选人，count=0（抵消一次）
7. 遇到 2：count=0，设置 candidate=2, count=1
最后 candidate 为 2。
复杂度分析
- 时间复杂度： $\displaystyle O(n)$ 。只需要对数组进行一到两次遍历。
- 空间复杂度： $\displaystyle O(1)$ 。只需要常数级别的额外空间来存储 candidate 和 count。
算法扩展

摩尔投票算法还可以扩展到寻找出现次数超过 $\displaystyle \frac{n}{k}$ 的元素。
例如，寻找出现次数超过 $\displaystyle \frac{n}{3}$ 的元素，此时最多会有 2 个这样的候选人。我们需要维护两个候选人和两个计数器，当遇到与两个候选人都不相等的元素时，两个计数器同时减 1。

代码实现

int find_main_number(int a[], int len) {
    if (a == NULL || len <= 0) {
        return -1;
    }
    int candidate = 0;
    int count = 0;

    for (int i = 0; i < len; i++) {
        if (count == 0) {
            candidate = a[i];
            count++;
        } else if (a[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }
    count = 0;
    for (int i = 0; i < len; i++) {
        if (a[i] == candidate) {
            count++;
        }
    }
    if (count > len / 2)
        return candidate;
    return -1;
}

int main() {
    // int a[] = {0, 5, 5, 3, 5, 7, 5, 5};
    int a[] = {0, 5, 5, 3, 5, 1, 5, 7};
    int main_number = find_main_number(a, sizeof(a) / sizeof(a[0]));
    printf("%d", main_number);
}

两次循环

复杂度分析的目的是为了区分不同“数量级”的算法。

$\displaystyle O(n)$ ：线性增长。即使是 $\displaystyle 10n$ $10 n$ （循环10次），它依然比 $\displaystyle O(n \log n)$ $O (n lo g n)$ （如排序算法）或 $\displaystyle O(n^2)$ $O (n^{2})$ （如嵌套循环）在数据量极大时快得多。
- 对比：
  - 如果 $\displaystyle n = 1,000,000$ ：
  - $\displaystyle O(2n)$ 大约执行 200 万次操作。
  - $\displaystyle O(n^2)$ 大约执行 1,000,000,000,000（一万亿）次操作。
  - 可以看到，多跑一轮循环带来的开销，在不同数量级的差距面前是微不足道的。

虽然两次循环在实际运行时间上确实比一次循环慢一点（大约慢一倍），但在算法理论层面，它依然属于最高效的线性时间复杂度 $\displaystyle O(n)$ ，这比任何基于排序（ $\displaystyle O(n \log n)$ ）的方法都要快。