摩尔选举求众数

介绍

博耶-摩尔多数投票算法（Boyer–Moore majority vote algorithm）,中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素的常数空间复杂度、线性时间复杂度算法。这一算法由罗伯特·S·博耶和J·斯特罗瑟·摩尔在1981年发表，也是处理数据流的一种典型算法。

图示

x轴为计数器中存储的元素，而下方y轴为输入的元素序列。遇到相同元素或者计数器中没有元素，计数器加入重复元素，如果遇到不同元素计数器消除一个元素。

---

算法示例

int majorityElement(vector<int>& nums) {
    int cnt = 0, now = nums[0], n = nums.size();
    for (int i = 0; i < n; i++){
        if(cnt == 0) now = nums[i];
        else if(now == nums[i]) cnt++;
        else cnt--;
    }
    return now;
}

---

算法分析

1. 时间复杂度 $O(n)$
2. 空间复杂度 $O(1)$

---

例题

1. leetcode 169.多数元素