[数据结构与算法]169. 多数元素、Leetcode的Go实现

博客主页：🏆看看是李XX还是李歘歘?🏆

🌺每天分享一些包括但不限于计算机基础、算法等相关的知识点🌺

💗点关注不迷路，总有一些📖知识点📖是你想要的💗

??今天的内容是Leetcode?169. 多数元素??💻💻💻

169. 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于?? n/2 ??的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例?1：

输入：[3,2,3]
输出：3

示例?2：

输入：[2,2,1,1,1,2,2]
输出：2

进阶：

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

方法1：map

先遍历一次，使用hash map存储元素出现的次数，再遍历hash map找出出现次数大于一半的元素：

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

方法2：排序

func majorityElement(nums []int) int {
    // 先排序，中间位置的数字就是多数元素
    sort.Ints(nums)
    return nums[(len(nums)-1)/2]
}

方法3：摩尔投票法

摩尔投票法(Boyer–Moore majority vote algorithm)，解决的问题是如何在任意多的候选人（选票无序），选出获得票数最多的那个。

使用result作为出现最多次的元素，count为其目前净累计[++和--]出现的次数，result出现一次count++，非result出现一次count--，当count==0时候，将result重新赋值给当前元素。

func majorityElement(nums []int) int {
    result,count:=0,0
    for _,v:=range nums{
        if count==0 {
            result = v
        }
        if v!=result{
            count--
        }else{
            count++
        }
    }
    return result
}