Boyer-Moore 投票算法

在刷 LeetCode 简单题的时候碰到了一道题，LeetCode 第 169 题 ，描述很简单：

1. 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
2. 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

其实一开始想到的就是排序找中位数，或者找众数，但是看题解之后才发现有更简单的 solution 。

Boyer-Moore 投票算法（摩尔投票算法），在题解的评论里看到一个对这个算法的描述，感觉非常贴切：同归于尽消杀法。其实核心思想非常简单：先维护一个数字和它出现的次数，当下个数字与这个数相同时，它出现的次数加 1 ，否则减 1 ，如果出现次数变为了 0 ，则将这个数字换成下一个遇到的数字。因为总是存在出现次数大于 ⌊ n/2 ⌋ 的元素，所以最后必定会得到一个数组，并且这个数字的出现次数大于 0 。

用 Golang 实现 Boyer-Moore 投票算法 解决上面的题目：

func majorityElement(nums []int) int {
	res, quantity := nums[0], 1
	for i := 1; i < len(nums); i++ {
		if res == nums[i] {
			quantity++
		} else {
			if quantity == 0 {
				res = nums[i]
			} else {
				quantity--
			}
		}
	}
	return res
}

虽然感觉这个算法的适用范围比较窄，不能找众数，只能找到 出现次数大 n/2 的元素 ，但是思想确实非常巧妙，对应解决这一类问题来说效率应该是最高的，时间复杂度为 \(O(n)\) ，空间复杂度为 \(O(1)\) 。