leetcode-169 主要元素

留言

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