LeetCode 169. 多数元素
题目描述
思路分析
我们可以使用 摩尔投票法 来解决这个问题。该算法的基本思路如下：
- 候选人选择：遍历数组，维护一个候选元素和一个计数器。初始时，候选元素为
null，计数器为 0。- 计数器更新：
- 如果计数器为 0，则将当前元素设为候选元素，并将计数器设为 1。
- 如果当前元素等于候选元素，则计数器加 1。
- 如果当前元素不等于候选元素，则计数器减 1。
- 最终结果：遍历结束后，候选元素即为多数元素。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func majorityElement(nums []int) int {
candidate, count := 0, 0
// 第一遍遍历，找到候选元素
for _, num := range nums {
if count == 0 {
candidate = num
count = 1
} else if num == candidate {
count++
} else {
count--
}
}
return candidate // 返回候选元素
}
- 时间复杂度：O (n)，其中 n 是数组的长度。我们只遍历了一次数组。
- 空间复杂度：O (1)，只使用了常数级别的额外空间。
1
write your code here
相似题目
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！