能否调整摩尔投票法查找出现次数≥n/2的数组元素？

首先看原有的摩尔投票法代码（用于查找出现次数>n/2的多数元素）：

for (int c = 0, i = 0; i < A.size(); i++)
    if (0 == c) {
        maj = A[i];
        c = 1;
    }
    else
        maj == A[i] ? c++ : c--;
return maj;
}

问题分析 #

原算法的核心是抵消思想：遍历数组时，遇到相同元素计数+1，不同则-1，计数归0时更换候选。对于出现次数>n/2的元素，它最终一定会成为候选且计数不为0，所以直接返回即可。但当需求改为出现次数≥n/2时，情况会变化：

• 比如数组[3,2,1,2,2,0]，2出现3次（n=6，3≥6/2），原算法执行后会返回2，刚好符合要求；
• 但如果数组是[3,2,3,2,1,0]，原算法会返回1，但1仅出现1次，不满足≥3的条件。

微调方案 #

可以通过原算法找到候选元素，但必须增加一步验证：

1. 用原算法遍历数组，得到候选元素maj；
2. 再次遍历数组，统计maj的出现次数；
3. 判断统计结果是否≥n/2：
   • 若是，返回maj；
   • 若否，说明不存在满足条件的元素（可根据需求返回特定值或做其他处理）。

调整后的示例代码 #

int findCandidate(vector<int>& A) {
    int c = 0, maj;
    for (int i = 0; i < A.size(); i++) {
        if (c == 0) {
            maj = A[i];
            c = 1;
        } else {
            c = (maj == A[i]) ? c + 1 : c - 1;
        }
    }
    return maj;
}

int findMajority(vector<int>& A) {
    int n = A.size();
    int candidate = findCandidate(A);
    // 验证候选元素的出现次数
    int count = 0;
    for (int num : A) {
        if (num == candidate) {
            count++;
        }
    }
    if (count >= n / 2) {
        return candidate;
    } else {
        // 不存在满足条件的元素，返回特定标识
        return -1;
    }
}

关键说明 #

• 原算法的遍历逻辑无需修改，它依然能筛选出可能满足≥n/2条件的候选；
• 验证步骤是必须的，因为当数组中没有元素满足≥n/2时，原算法会返回最后一次更换的候选，但该候选不满足要求。

内容的提问来源于stack exchange，提问作者a008