本文主要是介绍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(摩尔投票,清晰图解https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solutions/138691/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/
这篇关于LCR 158. 库存管理 II 哈希 / 摩尔投票法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!