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

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例: 

输入 1,2,3,2,2,2,5,4,2

输入 2

解题思路如下：

1. map存储

使用map结构存储存储字符出现的次数，其中key位数组中的字符，value为字符出现的次数，同时value值跟数组的一半长度比较，如果字符出现的次数大于或等于数组长度的一半，则返回该值

func getNumberByMap(arr []int) int {
	keyMap := map[int]int{}
	arrLen := len(arr)
	for _, v := range arr {
		if _, ok := keyMap[v]; !ok {
			keyMap[v] = 1
			continue
		}
		keyMap[v] ++

		if keyMap[v] > arrLen / 2 {
			return v
		}
	}
	return 0
}

2. 排序后取中间值

由于数组中有一个数字出现的次数超过数组长度的一半，即数字的长度>数组的length/2，所以对数组排序后，取数组的中位数返回即可

func getNumberBySort(arr []int) int {
	if len(arr) <= 0 {
		return 0
	}
	sort.Sort(sort.IntSlice(arr))
	i := len(arr) / 2
	return arr[i]
}

3. 相互抵消法

 由于数组中有一个数字出现的次数超过数组长度的一半，即该数组出现的总和>数组的length/2, 当让第一个数作为目标元素target，计数为count=1，若遇到相同元素，计数就+1，否则就-1。当计数为0时，让下一个元素作为目标元素，直到遍历完数组，当前目标元素返回即可。

func getNumberByCompare(arr []int) int {
	if len(arr) <= 0 {
		return 0
	}
	target := arr[0]
	count := 1
	for i := 1; i < len(arr); i++ {
		if count == 0 {
			target = arr[i]
			count = 1
			continue
		}
		if target == arr[i] {
			count++
		} else {
			count--
		}
	}
	return target
}

最后

以上就是落后蛋挞为你收集整理的找出数组中出现次数超过数组长度一半的数字的全部内容，希望文章能够帮你解决找出数组中出现次数超过数组长度一半的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。