剑指Offer 39. 数组中出现次数超过一半的数字
题目内容
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
1
2
3
4
5
6
7
8
9
| 示例?1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
?
限制：
1 <= 数组长度 <= 50000
|
解法一： 哈希表(暴力法)
思路：利用map存储，后遍历取出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int,int> cmap;
for(int num:nums){
cmap[num] += 1;
}
auto iter =cmap.begin();
while(iter != cmap.end())
{
if( iter->second>nums.size()/2){
return iter->first;
}
++iter;
}
return 0;
}
};
|
结果：
1
2
3
4
5
6
7
8
9
10
11
12
| 执行用时：
12 ms
, 在所有 C++ 提交中击败了
88.49%
的用户
内存消耗：
18.4 MB
, 在所有 C++ 提交中击败了
18.38%
的用户
通过测试用例：
45 / 45
|
此法继续优化，在第一个循环时检查是否超过一半，超过直接退出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int,int> cmap;
int temp = nums.size()/2;
for(int num:nums){
cmap[num] += 1;
if(cmap[num]>temp)return num;
}
auto iter =cmap.begin();
while(iter != cmap.end())
{
if( iter->second>temp){
return iter->first;
}
++iter;
}
return 0;
}
};
|
效率提升一般
1
2
3
4
5
6
7
8
9
10
11
12
| 执行用时：
12 ms
, 在所有 C++ 提交中击败了
88.49%
的用户
内存消耗：
18.3 MB
, 在所有 C++ 提交中击败了
67.94%
的用户
通过测试用例：
45 / 45
|
解法二：排序
思路：既然超过一半，中位数应该就是目标
1
2
3
4
5
6
7
| class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size()/2];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| 执行用时：
12 ms
, 在所有 C++ 提交中击败了
88.49%
的用户
内存消耗：
18.2 MB
, 在所有 C++ 提交中击败了
96.60%
的用户
通过测试用例：
45 / 45
|
解法三：摩尔投票法
思路：见 心法_摩尔投票法
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
int majorityElement(vector<int>& nums) {
int x = 0,votes = 0;
for(int num:nums){
if(votes==0)x=num;
votes += num == x ? 1: -1;
}
return x;
}
};
|
结果
1
2
3
4
5
6
7
8
9
10
11
12
| 执行用时：
8 ms
, 在所有 C++ 提交中击败了
98.07%
的用户
内存消耗：
18.4 MB
, 在所有 C++ 提交中击败了
22.42%
的用户
通过测试用例：
45 / 45
|
