多数元素

题目

169. 多数元素

解题思路

1. 直接暴力map
2. 排序，取中间节点的元素返回
3. 投票法，相同数字票数+1，否则减1，因为是多数元素，始终都能投出多数票

复杂度

1. 方法一
   1. 时间复杂度：O(n)
   2. 空间复杂度：O(n)
2. 方法二
   1. 时间复杂度：O(nlogn) ，为快排复杂度
   2. 空间复杂度：O(logn)
3. 方法三：
   1. 时间复杂度：O(n)
   2. 空间复杂度：`O(1) ## Code

方法一：

func majorityElement(nums []int) int {
    m := make(map[int]int)
	for _, v := range nums {
		m[v]++
		if m[v] > len(nums)/2 {
			return v
		}
	}
	return -1
}

方法二：

func majorityElement(nums []int) int {
	sort.Ints(nums)
	return nums[len(nums)/2]
}

方法三：

func majorityElement(nums []int) int {
	var (
		vote  int
		count int
	)
	for _, num := range nums {
		if count == 0 {
			vote = num
		}
		if vote == num {
			count++
		} else {
			count--
		}
	}
	return vote
}