【LeetCode & 剑指offer 刷题笔记】目录（持续更新中...）
39 数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
#include <unordered_map>
//
用
hash
表实现
using
namespace
std
;
//方法一：hash
表实现，
O
（
n
）
,O(n)
class
Solution
{
public
:
int
MoreThanHalfNum_Solution
(
vector
<
int
>
numbers
)
{
unordered_map
<
int
,
int
>
counter
;
int
k
=
numbers
.
size
()
/
2
;
for
(
int
ai
:
numbers
)
//
遍历数组
O(n)
{
counter
[
ai
]++;
//
构建计数器
if
(
counter
[
ai
]
>
k
)
return
ai
;
//
节省时间
}
// for(auto& n:counter) //
遍历计数器
O(k) ,
这里为
map
中的引用，不是指针，故直接用
n.first
// {
// if(n.second > k)
// {
// return n.first;
// }
// }
return
0
;
//
不存在
}
};
/*
方法二：“消解法”：如果一个数出现次数超过数组的一半，则其出现的次数比其他所有数字出现次数的和还要多，可以用两不同数之间进行消解，最后剩下的数即为出现次数最多那个数
缺点：需要判断是否真的次数超过一半，因为上述条件是必要条件但不是充分条件,时间效率没有hash表法好
O(n),O(1)
例：
1 2 2 2 3
i=0,t=0,res =1,t=1
i=1,不等，t-1=0
i=2,res =a[2] =2,t=1
i=3,相等，t+1=2
i=4,不等，t-1=1
*/
class
Solution
{
public
:
int
MoreThanHalfNum_Solution
(
vector
<
int
>
numbers
)
{
int
result
=
numbers
[
0
];
int
times
=
1
;
for
(
int
i
=
1
;
i
<
numbers
.
size
();
i
++)
{
if
(
times
==
0
) //候选数，
{
result
=
numbers
[
i
];
times
=
1
;
}
else
if
(
numbers
[
i
]
==
result
)
times
++;
//相等时次数加一，
else
times
--;
//不等时减一
}
times
=
0
;
for
(
int
ai
:
numbers
)//判断是否真的次数超过一半
{
if
(
ai
==
result
)
times
++;
}
if
(
times
>
numbers
.
size
()/
2
)
return
result
;
else
return
0
;
//不存在
}
};