题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000
示例1
输入
[1,2,3,2,2,2,5,4,2]
返回值
2
方法一:
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
| class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.empty())
return 0;
int time = 0;
int result = 0;
for(int i=0;i<numbers.size();i++)
{
if(time==0)
{
result = numbers[i];
time = 1;
}
else if(numbers[i]==result)
time++;
else
time--;
}
time = 0;
for(int i = 0;i<numbers.size();i++)
if(numbers[i]==result)
time++;
return time>numbers.size()>>1?result:0;
}
};
|
方法二:
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
map<int, int> mp;
for(const int val:numbers)
mp[val]++;
for(const auto &val:mp)
if(val.second > (numbers.size()>>1))
return val.first;
}
};
|