LCR 158.库存管理 I
难度：🟢 简单
标签：数组、哈希表、分治、排序、计数
链接：LCR 158. 库存管理 I (剑指 Offer 39. 数组中出现次数超过一半的数字)
题目描述
仓库管理员以数组 stock 形式记录商品库存数量。库存数量大于 stock.length / 2 的商品为畅销商品。请返回该畅销商品。
示例 1：
输入：stock = [6, 1, 3, 1, 1, 1]
输出：1
示例 2：
输入：stock = [1, 2, 6, 2, 2, 2, 3]
输出：2
解题思路
核心思想
本题的目标是找到数组中出现次数超过一半的元素（多数元素）。解决这个问题的核心思想有多种，但其中最巧妙且空间效率最高的是 摩尔投票法 (Boyer-Moore Voting Algorithm)。
思路选择
摩尔投票法 是解决此问题的最优思路。其核心理念是“对拼消耗”。
我们可以设想，把多数元素看作一方，把所有其他元素看作另一方。
从头开始遍历数组，我们维护一个候选元素
candidate和一个计数器count。当遇到一个与
candidate相同的数时，count加一。当遇到一个与
candidate不同的数时，count减一（相当于“同归于尽”）。如果
count减到 0，说明前面的数字已经完全被消耗掉了，我们就选择当前这个数作为新的candidate，并重置count为 1。
由于多数元素的数量超过了所有其他元素数量之和，所以在对拼消耗之后，最终留下的 candidate 一定是那个多数元素。
关键步骤
初始化：选择数组第一个元素作为初始的候选人
candidate，计数器count初始化为 1。循环遍历：从第二个元素开始遍历数组。 a. 如果当前元素与
candidate相同，则count加 1。 b. 如果当前元素与candidate不同，则count减 1。 c. 如果count减为 0，则更换候选人，将candidate设为当前元素，并将count重新设为 1。返回结果：遍历结束后，
candidate中存储的就是多数元素，返回即可。
代码实现 (推荐)
/**
* @param {number[]} stock
* @return {number}
*/
var inventoryManagement = function (stock) {
let candidate = stock[0];
let count = 1;
for (let i = 1; i < stock.length; i++) {
// 如果计数为0，更换候选人
if (count === 0) {
candidate = stock[i];
count = 1;
} else if (stock[i] === candidate) {
// 遇到相同的数，计数加一
count++;
} else {
// 遇到不同的数，计数减一
count--;
}
}
return candidate;
};
原始代码分析 (用户提供)
您提供的代码完全正确地实现了摩尔投票算法的核心逻辑。
/**
* @param {number[]} stock
* @return {number}
*/
var inventoryManagement = function (stock) {
// 候选人和其票数
let maxCount = 1;
let maxValue = stock[0];
for (let i = 1; i < stock.length; i++) {
// 如果当前商品与候选人相同，票数增加
if (stock[i] === maxValue) {
maxCount++;
} else {
// 如果不同，票数减少（对拼消耗）
maxCount--;
// 如果票数耗尽，更换候选人
if (maxCount === 0) {
maxValue = stock[i];
maxCount = 1;
}
}
}
return maxValue;
};
优点：逻辑清晰，完全符合摩尔投票算法的思想，时空效率都很高。
代码风格：变量名
maxValue和maxCount虽能工作，但使用candidate和count更能体现“候选人”和“票数”这一算法模型的精髓，可读性稍好一些。推荐代码中调整了if-else的顺序，先判断count是否为0，使得逻辑分支更清晰。
复杂度分析
时间复杂度：O(n) 其中 n 是数组
stock的长度。我们只需要对数组进行一次完整的遍历。空间复杂度：O(1) 我们只使用了常数个额外变量，空间消耗是恒定的。
相关题目
总结
本题的摩尔投票算法是一个非常精妙的解法，它通过一种“对抗消耗”的思路，在一次遍历和常数空间内找到了多数元素。这个算法是处理“寻找出现次数超过特定阈值的元素”这类问题的强大工具。