关于golang:Golang力扣Leetcode中级算法其他多数元素哈希表摩尔投票法

题目：给定一个大小为 n 的数组，找到其中的少数元素。少数元素是指在数组中呈现次数 大于 ⌊ n/2 ⌋ 的元素。

你能够假如数组是非空的，并且给定的数组总是存在少数元素。

链接： 力扣Leetcode—中级算法—其余—少数元素.

示例 1：

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

示例 2：

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

标签：数组、哈希表、分治、计数、排序

思路：简略的想法是应用哈希表或者排序实现，遍历一次数组，将每个数呈现的次数存入哈希表，当次数大于n/2时返回即可，代码如下：

全副Go代码如下：

package mainimport (    "fmt")func majorityElement(nums []int) int {    var res int    m := make(map[int]int)    n := len(nums)    if n < 1 {        return 0    } else if n == 1 {        return nums[0]    } else {        for _, v := range nums {            m[v]++        }        for key, v := range m {            if v > n/2 {                res = key                break            } else {                continue            }        }        return res    }}func main() {    a := []int{8, 8, 7, 7, 7}    fmt.Println(majorityElement(a))}

提交截图：

然而该计划空间复杂度为O(n)，不符合要求O(1)

咱们还能够用 摩尔投票的思维 ，对拼耗费，就能够满足空间复杂度为O(1)的要求。

• 遍历整个数组，从第一个数开始，count = 1，遇到雷同的就加1，遇到不同的就减1
• 减到0，从下一个数开始计数。
• 因为少数元素的数量超出半数，最终剩下的肯定就是少数元素

代码如下：

package mainimport (    "fmt")func majorityElement(nums []int) int {    count := 1    major := nums[0]    for i := 1; i < len(nums); i++ {        if major == nums[i] {            count++        } else {            count--            if count == 0 {                major = nums[i+1]            }        }    }    return major}func main() {    a := []int{8, 8, 7, 7, 7}    fmt.Println(majorityElement(a))}