LCR 158. 库存管理 II 哈希 / 摩尔投票法

库存管理 II 哈希 / 摩尔投票法"/>

LCR 158. 库存管理 II 哈希 / 摩尔投票法

LCR 158. 库存管理 II - 力扣（LeetCode）

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

（1）方法一：先排序

题目说存在数的出现次数大于一半，所以排完序之后，返回中间位置对应的数就可行了

class Solution {
public:int inventoryManagement(vector<int>& stock) {sort(stock.begin(),stock.end());// 先排序return stock[stock.size() >> 1];}
};

 （2）方法二：哈希表

class Solution {
public:int inventoryManagement(vector<int>& stock) {int num = stock.size() >> 1;unordered_map<int,int> mp;for(const int &a:stock) {mp[a]++;if(mp[a]>num) return a;}return -1;}
};

（3）方法三：摩尔投票法

class Solution {
public:int inventoryManagement(vector<int>& stock) {int votes = 0;int x = 0;for(const int &num : stock) {if(votes==0) x=num;// if(x==num) votes++;// else votes--;votes += (x==num)? 1 : -1;}return x;}
};

推荐和参考文章：

LCR 158. 库存管理 II（摩尔投票，清晰图解/