1.1. 题目
1.1.1. 求众数
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
1.1.2. 题解:
- 题目没有时间和空间复杂度要求,所以解法就很多了
- 众数是大于整体数量的一半的
- 数组没有顺序
1.1.3. 思路:
- 看完题,我自己想到了两种简单的解法
- map存每个数字出现的次数,然后取其中 大于 count/2 的数,就是众数
- 把数组排序,然后取 数组 1/2 下标的值肯定就是众数了.. 因为这个众数数量大于总数的一半,所以排序后的数组 下标最中间的那个值肯定是众数
- 看了官方题解,其他的都差不多,方法很多,不过看到最后一个投票方法很不错
- 假如众数为 +1,非众数都是 -1, 那么所有的和肯定是正数
- 从头开始,比如先定义第一个数为众数,那么众数+1,如果下一个数跟第一个数不一样,那么就减一,那么此时,和为零了,那么下一个数就是新的假设的众数
- 如果第二个数跟假设的定数一样,那么就 +1, 一旦 和为零的时候,把下一个值新定义成一个众数,最后得出的 定义的众数就是真实的众数
- 不过这个条件比较苛刻,比如 众数的数量是必须大于 总数的一半的,否则这个做法是不对的,比如
1,1,1,2,2,2,3,3,1这种情况
1.1.4. 代码:
点击显示
func majorityElement(nums []int) int {
// 定义s为 和, sign为假设的众数
var s,sign int
numLen := len(nums)
for i:=0;i<numLen;i++ {
// 当和为0时,重新设置一个众数
if s == 0 {
sign = nums[i]
}
// 当当前数和假设的众数一样,就加一,否则减一
if nums[i] == sign {
s++
} else {
s--
}
}
fmt.Println(s,sign)
return sign
}
func majorityElement1(nums []int) int {
// 直接给数组排序,取数组中间值
sort.Ints(nums)
return nums[len(nums)/2]
}
func majorityElement2(nums []int) int {
// 定义一个map存储每个数字的次数
numMap := make(map[int]int)
numLen := len(nums)
for i:=0;i<numLen;i++ {
numMap[nums[i]]++
}
// 找出次数大于 总数一半的
for m,n := range numMap {
if n > numLen/2 {
return m
}
}
return 0
}