投票算法 Boyer-Moore

Lily Flower / 2024-09-25 / 原文

投票算法 Boyer-Moore

算法描述

Boyer-Moore 投票算法是一种用来在线性时间内找到数组中出现次数超过一半（即多数元素）的算法。这个算法非常高效，因为它只需要一次遍历数组，并且使用常数级别的额外空间。

leetcode169题: 多数元素

算法思路

维护一个候选元素和一个计数器来实现投票算法：

初始化一个候选者 candidate 和一个计数器 count
遍历整个数组：
1. 如果 count 为 0，那么将当前元素设为 候选者，并设置该候选者的计数器 count 为 1。
2. 如果当前正在遍历的元素就是此时的候选者，那么该候选器的计数器count+1。
3. 如果当前遍历的元素并不是此时的候选者，那么减少该候选器的计数器值-1。
当遍历完成时，候选器candidate就是我们要找的多数元素。

算法实现

public int majorityElement(int[] nums) {
    int candidate = 0x00;   // 候选者
    int counter = 0;    // 候选者的支持度(计数器)

    for (int e: nums) {
        if (counter == 0) {
            // 如果当前计数器为0，设置当前正在遍历的元素为候选者
            candidate = e;
            // 设置当前元素的支持度为1
            counter = 1;
        } else if (e == candidate) {
            // 当前元素就是该候选者，计数器+1
            counter++;
        } else {
            // 当前元素不是该候选者，计数器-1
            counter-- ;
        }
    }

    return candidate;
}

复杂度分析

时间复杂度