39.md

数组中出现次数超过一半的数字

题目

• 给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字
• 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]
• 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2

数据范围：n≤50000，数组中元素的值 0≤val≤10000 要求：空间复杂度：O(1)，时间复杂度 O(n)

输入描述：保证数组输入非空，且保证有解

示例

• 输入：[1,2,3,2,2,2,5,4,2]
• 返回值：2

实现

func MoreThanHalfNum_Solution(numbers []int) int {
	res := 0
	limit := len(numbers)/2 + 1
	record := make(map[int]int)
	for _, v := range numbers {
		record[v] += 1
		if record[v] == limit {
			res = v
		}
	}
	return res
}