关于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 main

import ("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 main

import ("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))
}