摩尔投票算法（Boyer-Moore Voting Algorithm）由 Robert Boyer 和 J Strother Moore 在 1981 年提出，最初的目的是为了解决寻找序列中多数元素（即出现次数超过一半的元素）的问题。其核心思想是通过 “投票” 机制来高效地找出这个元素。
主要思想
如果一个元素是多数元素，那么它的出现次数比其他所有元素的总和还要多。因此，可以通过一种巧妙的方式“抵消”掉不同的元素，最终剩下的就可能是多数元素。具体步骤如下：
- 初始化：设置一个候选元素
candidate和计数器count。初始时，count设为0 - 遍历数组：
- 当
count为0时，选择当前元素作为新的候选元素candidate - 如果当前元素等于
candidate，则count++ - 如果当前元素不等于
candidate，则count--
- 当
- 验证候选元素：在第一次遍历完成后，
candidate是潜在的多数元素，但为了确保它是真正的多数元素，我们需要进行第二次遍历来确认其出现次数是否确实超过数组长度的一半。
时间与空间复杂度
时间复杂度：O(n)，因为算法只需要两次遍历数组。
空间复杂度：O(1)，仅使用了常数级别的额外空间来存储 candidate 和 count。
应用
Leetcode 169 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
作答：
在数组中出现次数大于 ⌊ n/2 ⌋ 的元素，一个数组中最多存在一个元素是大于n/2的
package main
import "fmt"
// 摩尔投票算法
func majorityElement(nums []int) int {
// 候选元素，初始化为任意值
candidate := -1
// 计数器，初始化为 0
count := 0
// 第一遍遍历，寻找可能的众数
for _, num := range nums {
if count == 0 {
// 选择一个新的候选元素
candidate = num
}
if num == candidate {
// 当前元素与候选元素相同，计数器加 1
count++
} else {
// 当前元素与候选元素不同，计数器减 1
count--
}
}
// 第二遍遍历，确认候选元素是否真的是众数
count = 0
for _, num := range nums {
if num == candidate {
count++
}
}
// 如果候选元素出现次数超过一半，返回该元素
if count > len(nums)/2 {
return candidate
}
// 如果没有众数，返回 -1
return -1
}
func main() {
nums := []int{3, 2, 3}
fmt.Println(majorityElement(nums)) // 输出 3
}
Leetcode 229 多数元素 II
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：nums = [3,2,3]
输出：[3]
示例 2：
输入：nums = [1]
输出：[1]
示例 3：
输入：nums = [1,2]
输出：[1,2]
提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
作答：
在数组中出现次数大于 ⌊ n/3 ⌋ 的元素，一个数组中最多存在两个元素是大于n/3的
package main
import "fmt"
func main() {
fmt.Println(majorityElement([]int{1, 2, 1, 2, 3}))
}
func majorityElement(nums []int) []int {
res := make([]int, 0)
// 候选元素，初始化为任意值 计数器，初始化为 0
candidate1, count1, candidate2, count2 := 0, 0, 0, 0
for i := 0; i < len(nums); i++ {
// 避免统计重复
if (count1 == 0 || nums[i] == candidate1) && candidate2 != nums[i] {
count1++
candidate1 = nums[i]
} else if count2 == 0 || nums[i] == candidate2 {
count2++
candidate2 = nums[i]
} else {
count1--
count2--
}
}
// 校验是否正确
count1, count2 = 0, 0
for _, v := range nums {
if v == candidate1 {
count1++
}
if v == candidate2 {
count2++
}
}
if count1 > len(nums)/3 {
res = append(res, candidate1)
}
if count2 > len(nums)/3 && candidate1 != candidate2 {
res = append(res, candidate2)
}
return res
}
摩尔投票的思想就是要寻找一个数组中出现次数最多的元素，然后在校验是否符合预期。这样的想法主要就是降低了空间复杂度，这篇的文章分享就到这里啦，如果文章对你有帮助，点赞+收藏～～