169. Majority Element

中文版: 主要元素


Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

常规做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

func majorityElement(nums []int) int {

m := make(map[int]int)

for _, v := range nums {

if _, ok := m[v]; ok {

m[v] = m[v] + 1

} else {
m[v] = 1
}

if len(nums) < 2*m[v] {
return v
}

}
return 0
}

时间复杂度为O(n), 引入了一个map,空间复杂度为O(n)


进阶做法

你有办法在时间复杂度为 O(N),空间复杂度为 O(1) 内完成吗?

1
2