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

示例 1：

**输入：**stock = [6, 1, 3, 1, 1, 1]
**输出：**1

提示：

1 <= stock.length <= 50000

给定数组为非空数组，且存在结果数字

直接使用哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int inventoryManagement(vector<int>& stock) {
unordered_map<int, int> hash;
int len = stock.size();
for (int i : stock) {
hash[i]++;
if (hash[i] > len / 2)
return i;
}
return -1;
}
};

摩尔投票

假设现在进行投票，我们要选出票数最多的人，并且此人票数比其他所有人加一块都要多

如果A获得一票，B再获得一票，此时可以认为A与B的两票抵消了，同理只要是不同的候选人，票数都可以相互抵消；

所以可以直接先指定一个胜利者，将其他人的票与此人抵消，当票数抵消为0时，再选择下一位候选人为胜利者，因为“众数”出现的次数超过了总数的一半，所以即使它和其他所有非众数的人一对一抵消，最后剩下的也一定是那个众数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int inventoryManagement(vector<int> &stock) {
        int ansid = 0;
        int num = 0;
        for (int i = 0; i < stock.size(); i++) {
            if (num == 0)
                ansid = i;
            if (stock[i] == stock[ansid])
                num++;
            else
                num--;
        }
        return stock[ansid];
    }
};