# 题目链接
# 题目描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
1
2
2
# 解题思路
- 假设当前数为众数, 遇到相同的数字则加一,否则减一
- 若前n个票和为0(互相抵消), 则设下一个数为当前数
- 重复1, 2 最后的当前数为众数
func majorityElement(nums []int) int {
vote := 0
x := nums[0]
for _, num := range nums {
// 票数抵消
if vote == 0 {
// 假设当前数为众数
x = num
}
if num == x {
// 投正票
vote += 1
} else {
// 投反票
vote -= 1
}
}
return x
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19