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

77 阅读 0 评论 51 点赞

我是靠谱客的博主落后蛋挞，这篇文章主要介绍找出数组中出现次数超过数组长度一半的数字，现在分享给大家，希望可以做个参考。

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

示例:

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

输入 2

解题思路如下：

1. map存储

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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，所以对数组排序后，取数组的中位数返回即可

复制代码

1
2
3
4
5
6
7
8
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时，让下一个元素作为目标元素，直到遍历完数组，当前目标元素返回即可。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
}