[LeetCode][LCR158]库存管理 II——摩尔投票法

题目

LCR 158. 库存管理 II

仓库管理员以数组 stock 形式记录商品库存表。stock[i] 表示商品 id，可能存在重复。请返回库存表中数量大于 stock.length / 2 的商品 id。

• 示例 1:

输入: stock = [6, 1, 3, 1, 1, 1]
输出: 1

• 限制：
  1 <= stock.length <= 50000
  给定数组为非空数组，且存在结果数字

• 注意：本题与主站 169 题相同：传送门

思考

1. 本题要求找到个数超过一半的数字
2. 最简单的方法就是遍历一遍，使用一个哈希表统计
3. 也可以进行排序，中点处肯定就是目标数字
4. 这道题由于要找的数字是超过一半的数字，那么很容易知道其实该数字即使和其他数字相消，最后也会留下至少一个该数字
5. 这种思想称为摩尔投票法

解法

1. 摩尔投票法的关键在于抵消，在算法的执行过程中，当遇到不同的元素时，当前的候选者票数减一的行为。这意味着如果遇到两个不同的元素，它们会相互抵消掉一部分影响，从而保持着候选者的相对优势。这种抵消行为有助于最终确定出现次数超过一半的元素
2. 我们遍历数组，维护一个候选者和对应的票数。遇到相同的元素时，候选者的票数加一，遇到不同的元素时，候选者的票数减一。如果候选者的票数变为零，我们选择当前遍历到的元素作为新的候选者。这样，最终留下来的候选者就有可能是出现次数超过一半的元素

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int vote=0, curMode;
        for(auto &ele:nums){
            if(!vote) curMode=ele;
            vote += curMode==ele ? 1 : -1;
        }
        return curMode;
    }
};