LeetCode 剑指 Offer 39. 数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1： 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2
提示：
- 1 <= 数组长度 <= 50000
- 数组中的数字范围是 -10^9 到 10^9
思路分析
思路描述
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func inventoryManagement(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
许可协议，转载请注明出处！