AC106-主元素查找算法¶

已知整数序列 A = {a₀, a₁, ..., aₙ₋₁}，其中 0 ≤ aᵢ < n（0 ≤ i < n）。若一个整数序列中某个元素出现的次数超过序列长度的一半，则称其为主元素。例如，A = (0, 5, 5, 3, 5, 7, 5, 5)，则 5 为主元素；又如 A = (0, 5, 5, 3, 5, 1, 5, 7)，则 A 没有主元素。设计尽可能高效的算法找出数组 A 中的主元素，若存在主元素则输出该元素，否则输出 -1。（2013 年统考题）

问题分析¶

给定一个整数序列 A，其中每个元素满足 0 ≤ ai < n（n 为数组长度）。要求设计一个尽可能高效的算法，判断是否存在主元素（即出现次数超过 n/2 的元素），并返回主元素的值。如果不存在主元素，则返回 -1。

实现代码¶

方法 1：计数法（基于哈希表思想）¶

C
/**
 * 查找主元素 - 使用计数法
 * @param A[] 输入数组
 * @param n   数组长度
 * @return 存在主元素时返回其值，否则返回 -1
 */
int func(int A[], int n) {
    // 边界检查：空数组或单元素数组
    if (n <= 0) return -1;

    // 分配计数数组 B，大小为 n
    int *B = (int *)malloc(sizeof(int) * n);
    if (B == NULL) return -1;  // 内存分配失败

    // 初始化计数数组为 0
    for (int i = 0; i < n; i++) {
        B[i] = 0;
    }

    // 统计每个元素的出现次数
    for (int i = 0; i < n; i++) {
        B[A[i]]++;
    }

    // 查找是否有元素出现次数超过 n/2
    for (int i = 0; i < n; i++) {
        if (B[i] > n / 2) {
            free(B);  // 释放动态分配的内存
            return i;  // 返回主元素
        }
    }

    free(B);  // 释放动态分配的内存
    return -1;  // 不存在主元素
}

方法 2：摩尔投票法（Boyer-Moore Voting Algorithm）¶

C
/**
 * 查找主元素 - 使用摩尔投票法
 * @param A[] 输入数组
 * @param n   数组长度
 * @return 存在主元素时返回其值，否则返回 -1
 */
int funcOptimized(int A[], int n) {
    // 边界检查：空数组或单元素数组
    if (n <= 0) return -1;

    // 第一步：寻找候选主元素
    int candidate = -1, count = 0;
    for (int i = 0; i < n; i++) {
        if (count == 0) {
            candidate = A[i];  // 更新候选主元素
            count = 1;
        } else if (A[i] == candidate) {
            count++;  // 当前元素与候选主元素相同，计数加 1
        } else {
            count--;  // 当前元素与候选主元素不同，计数减 1
        }
    }

    // 第二步：验证候选主元素是否确实为主元素
    count = 0;
    for (int i = 0; i < n; i++) {
        if (A[i] == candidate) {
            count++;
        }
    }

    // 如果候选主元素出现次数超过 n/2，则返回它
    if (count > n / 2) {
        return candidate;
    }

    return -1;  // 不存在主元素
}

算法执行过程图解¶

示例 1：存在主元素¶

输入数组：A = [0, 5, 5, 3, 5, 7, 5, 5]

方法 1：计数法¶

初始化计数数组 B：
Text Only
1
B = [0, 0, 0, 0, 0, 0, 0, 0]
统计每个元素的出现次数：
Text Only
1
B = [1, 0, 0, 1, 0, 5, 0, 1]
检查是否有元素出现次数大于 n/2 = 4：
B[5] = 5 > 4，返回 5。

方法 2：摩尔投票法¶

寻找候选主元素：
Text Only
1
candidate = 5, count = 4
验证候选主元素：
Text Only
1
count = 5 > 4，返回 5

示例 2：不存在主元素¶

输入数组：A = [0, 5, 5, 3, 5, 1, 5, 7]

方法 1：计数法¶

初始化计数数组 B：
Text Only
1
B = [0, 0, 0, 0, 0, 0, 0, 0]
统计每个元素的出现次数：
Text Only
1
B = [1, 1, 0, 1, 0, 4, 0, 1]
检查是否有元素出现次数大于 n/2 = 4：
无元素满足条件，返回 -1。

方法 2：摩尔投票法¶

寻找候选主元素：
Text Only
1
candidate = 5, count = 3
验证候选主元素：
Text Only
1
count = 4 <= 4，返回 -1

复杂度分析¶

方法 1：计数法¶

时间复杂度：O(n)¶

统计阶段：遍历数组一次，时间复杂度为 O(n)。
查找阶段：遍历计数数组一次，时间复杂度为 O(n)。
总时间复杂度：O(n)。

空间复杂度：O(n)¶

需要额外的计数数组 B，大小为 n。
空间复杂度：O(n)。

方法 2：摩尔投票法¶

时间复杂度：O(n)¶

寻找候选主元素：遍历数组一次，时间复杂度为 O(n)。
验证候选主元素：再遍历数组一次，时间复杂度为 O(n)。
总时间复杂度：O(n)。

空间复杂度：O(1)¶

只使用了常数个额外变量（candidate 和 count）。
空间复杂度：O(1)。

关键知识点延伸¶

1. 摩尔投票法原理¶

摩尔投票法是一种巧妙的算法，用于在线性时间内找到可能的主元素。其核心思想是： - 消除对冲：如果两个不同的元素相遇，则它们相互抵消。 - 保留候选：最终剩下的候选元素可能是主元素。

正确性证明¶

假设主元素存在，其出现次数超过 n/2。
在消除过程中，主元素不会被完全抵消，因为其他元素的数量不足以抵消它。
最终剩下的候选元素就是主元素。

2. 扩展应用¶

2.1 查找多个主元素¶

如果需要查找多个主元素（即出现次数超过 n/k 的元素），可以使用扩展的摩尔投票法：

C
void findMajorityElements(int A[], int n, int k) {
    // 实现略
}

2.2 不限制元素范围¶

如果元素范围不限制在 [0, n-1]，可以使用哈希表代替计数数组：

C
int funcUnrestricted(int A[], int n) {
    // 使用哈希表记录频率
}

3. 特殊情况处理¶

3.1 空数组或单元素数组¶

C
if (n <= 0) return -1;
if (n == 1) return A[0];

3.2 全部元素相同¶

C
1 2	`// 输入: [5, 5, 5, 5, 5] // 输出: 5`

3.3 无主元素¶

C
1 2	`// 输入: [0, 1, 2, 3, 4] // 输出: -1`

算法特点总结¶

方法 1：计数法¶

简单直观：逻辑清晰，易于实现。
空间代价高：需要额外的计数数组。
适用场景：元素范围受限且空间充足的情况。

方法 2：摩尔投票法¶

高效性：时间复杂度 O(n)，空间复杂度 O(1)。
通用性：适用于任意范围的元素。
简洁性：实现简单，逻辑优雅。

记忆要点¶

计数法：利用额外数组统计频率，适合元素范围有限的情况。
摩尔投票法：通过抵消策略找到候选主元素，再验证其是否为主元素。
时间效率：两种方法均为 O(n)，但摩尔投票法更节省空间。
空间效率：计数法需要 O(n)，摩尔投票法仅需 O(1)。
边界处理：注意空数组、单元素数组和无主元素的情况。