题目描述
数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。
1
2
3
4
5
6
7
8
9
10
11
示例1
输入：[1,2,5,9,5,9,5,5,5]
输出：5
示例2
输入：[3,2]
输出：-1
示例3
输入：[2,2,1,1,1,2,2]
输出：2
思路
看完题第一个反应是直接搞一个hashmap，用空间换时间，但是题目要求空间复杂度O(1)，所以要用摩尔投票法解决。
摩尔投票法的主要思路是这样，假设有一个规则特殊的战场，战场上有N支人数各异的军队，该战场同时只能容纳两人上场战斗，且士兵战斗力相同只能用1换1的方式解决对方。
这样一来，最后获胜的军队共有两种可能性，一是该军队人数超过该战场人数的一半，无情碾压获得胜利；另一种则是有一支人数不占优势的军队一直在苟，等其他军队互相消耗的差不多之后，依靠苟出来的优势获得胜利（鹬蚌相争渔翁得利的感觉）。
由于题目要求要找出占比超过一半的元素，所以最后需要判断胜利者的军队人数是否超过战场总人数的一半。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
int majorityElement(vector<int>& nums) {
int win;
int counter = 0;
for (int n: nums)
{
if (counter == 0)//此时战场上没有士兵
{
win = n;
counter++;
}
else
{
if (n == win)//如果第二个上场士兵的和前一个是同一个军队
counter++;
else//不是同一军队，1换1
counter--;
}
}
if (counter != 0)
{
counter = 0;
for (int n: nums)
{
if (n == win)
counter++;//求出获胜军队人数
}
}
return (counter > (nums.size() / 2)) ? win : -1;//判断获胜军队人数是否超过战场总人数一半
}
};
