LeetCode，数组中有一个数超过元素的一半，找出那个数

力扣题目：

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/majority-element

解题

1. 哈希表

我们最容易想到的方法就是使用一个哈希表来存储每个元素，键表示一个元素，值表示该元素出现的次数。然后，我们遍历哈希映射中的所有键值对，返回值最大的键。对于题目要求空间复杂度为 O(1) 的算法解决此问题。此哈希表的方法我们就略过。

2. 摩尔投票法

摩尔投票法（Boyer–Moore majority vote algorithm），也被称作「多数投票法」，该算法解决的问题是：如何在任意多的候选人中（选票无序），选出获得票数最多的那个。

思路：

• 随便选个人当选，和他相同就赞成，票数++
• 和它不同就反对，票数–-
• 票数为0则换一个候选人，最终票数肯定是正的，当选的便是众数

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

❝注意：这种解法只是满足于超过一半的投票，众数过半，抵消之后，剩下的就是答案。 ❞