多数元素

怎样从“nums=[2,2,1,1,1,2,2],找出出现次数超过 ⌊n/2⌋ 的多数元素,答案是 2。直觉:多数元素出现次数超过一半,比其他所有元素加起来还多。”推导出 Boyer-Moore 投票 · 候选人/票数抵消 · 空间 O(1)，并证明每次状态变化都不会漏掉答案？

中心结论：维护候选人 candidate 与净票数 count:count 为 0 时把当前元素设为 candidate;当前元素等于 candidate 则 count+1,否则 count-1。多数元素和其他元素两两抵消后仍会剩下,所以扫描结束时的 candidate 就是答案。

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

在本站主例中，nums=[2,2,1,1,1,2,2],找出出现次数超过 ⌊n/2⌋ 的多数元素,答案是 2。直觉:多数元素出现次数超过一半,比其他所有元素加起来还多。

算法最终需要得到或观察：扫描 [2,2,1,1,1,2,2],投票抵消后 candidate=2,返回 2。

逐对枚举能够得到答案，但同一个查找会发生许多次；哈希表把已经见过的信息保存成一次查询。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“哈希记忆表”，明确答案需要观察什么。
2. 2状态只维护 candidate(候选人)、count(净票数)、current(当前值)、index(下标)。
3. 3转移每一步按照 维护候选人 candidate 与净票数 count:count 为 0 时把当前元素设为 candidate;当前元素等于 candidate 则 count+1,否则 count-1。多数元素和其他元素两两抵消后仍会剩下,所以扫描结束时的 candidate 就是答案。
4. 4收尾读取 扫描 [2,2,1,1,1,2,2],投票抵消后 candidate=2,返回 2。，并复核边界与复杂度。

先问未来需要查询什么，再决定 map 的 key 与 value。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：candidate(候选人)、count(净票数)、current(当前值)、index(下标)。

题目要求找出数组中出现次数大于 `⌊ n/2 ⌋` 次的数。要求空间复杂度为 O(1)。简单题。 这一题利用的算法是 Boyer-Moore Majority Vote Algorithm。https://www.zhihu.com/question/49973163/answer/235921864

维护候选人 candidate 与净票数 count:count 为 0 时把当前元素设为 candidate;当前元素等于 candidate 则 count+1,否则 count-1。多数元素和其他元素两两抵消后仍会剩下,所以扫描结束时的 candidate 就是答案。

执行过程中持续维护：candidate(候选人)、count(净票数)、current(当前值)、index(下标)。

正确性依赖以下不变量：count 始终等于当前 candidate 在「还没被抵消」的元素里的净票数;count 归零代表前面这一段已两两抵消干净。；多数元素出现次数 > ⌊n/2⌋,和其他所有元素一一抵消后仍有剩余。

面试时可以压缩为：这题最直观可以用哈希表统计频次，时间 O(n)、空间 O(n)。更优解是 Boyer-Moore 投票法：维护 candidate 和 count。遇到相同元素 count++，遇到不同元素 count--，count 为 0 时更换候选人。因为多数元素出现次数超过一半，它和其他元素抵消后仍会剩下，所以最终 candidate 就是多数元素。时间 O(n)，空间 O(1)。

落到当前题，执行机制可以压缩为：维护候选人 candidate 与净票数 count:count 为 0 时把当前元素设为 candidate;当前元素等于 candidate 则 count+1,否则 count-1。多数元素和其他元素两两抵消后仍会剩下,所以扫描结束时的 candidate 就是答案。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入nums=[2,2,1,1,1,2,2],找出出现次数超过 ⌊n/2⌋ 的多数元素,答案是 2。直觉:多数元素出现次数超过一半,比其他所有元素加起来还多。 因为：维护候选人 candidate 与净票数 count:count 为 0 时把当前元素设为 candidate;当前元素等于 candidate 则 count+1,否则 count-1。多数元素和其他元素两两抵消后仍会剩下,所以扫描结束时的 candidate 就是答案。
2. 2朴素解法:哈希计数最直观的办法:开一张哈希表数每个值出现几次,谁的次数超过 ⌊n/2⌋,谁就是多数元素。 因为：哈希计数一定能得到答案,但要额外开一张和数组一样大的表,空间是 O(n)——这正是我们想优化掉的。
3. 3count=0 → 选 candidatecount 现在是 0,说明手上没有候选人。把当前元素 2 设为 candidate,count 置 1。 因为：没有候选人时,当前元素先顶上当候选人;如果它其实不是多数元素,后面会被一一抵消掉。
4. 4current==candidate → count++当前元素 2 和 candidate 相同,相当于多一张支持票,count 加到 2。 因为：相同元素给 candidate 投赞成票,净票数 count 越大,candidate 越难被抵消掉。
5. 5current!=candidate → count--当前元素 1 和 candidate 不同,相当于一次抵消,count 减到 1。 因为：不同元素抵消掉 candidate 的一张净票;只要 count 还大于 0,candidate 就暂时守得住。
6. 6预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
7. 7正确性解释题目保证多数元素一定存在,所以扫描结束时的 candidate 就是它,直接返回 2。 因为：多数元素的出现次数超过 n/2。把一个多数元素和一个非多数元素配对删除，多数元素仍然不会被完全删光。Boyer-Moore 的 count 表示当前 candidate 在未抵消部分中的净票数。当 count 归零，说明前面这一段已经完全抵消，可以从下一个元素重新选择候选人。由于题目保证多数元素存在，最终留下的 candidate 就是答案。
8. 8收尾与复杂度扫描 [2,2,1,1,1,2,2],投票抵消后 candidate=2,返回 2。 因为：时间 O(n) · 空间 O(1)。维护候选人 candidate 与净票数 count:count 为 0 时把当前元素设为 candidate;当前元素等于 candidate 则 count+1,否则 count-1。多数元素和其他元素两两抵消后仍会剩下,所以扫描结束时的 candidate 就是答案。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一 时间复杂度 O(n) 空间复杂度 O(1)
func majorityElement(nums []int) int {
	res, count := nums[0], 0
	for i := 0; i < len(nums); i++ {
		if count == 0 {
			res, count = nums[i], 1
		} else {
			if nums[i] == res {
				count++
			} else {
				count--
			}
		}
	}
	return res
}

// 解法二 时间复杂度 O(n) 空间复杂度 O(n)
func majorityElement1(nums []int) int {
	m := make(map[int]int)
	for _, v := range nums {
		m[v]++
		if m[v] > len(nums)/2 {
			return v
		}
	}
	return 0
}

func main() {
    // 1. 主例
    //    输入：mode="majority", nums=[2,2,1,1,1,2,2]
    //    期望：扫描 [2,2,1,1,1,2,2],投票抵消后 candidate=2,返回 2。
    //
    // 2. 失败 / 未命中
    //    检查：count 不是 candidate 的真实出现次数，而是抵消后的净票数。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC229 多数元素 II；LC347 前 K 个高频元素；LC217 存在重复元素
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意nums=[2,2,1,1,1,2,2],找出出现次数超过 ⌊n/2⌋ 的多数元素,答案是 2。直觉:多数元素出现次数超过一半,比其他所有元素加起来还多。
2. 2重复逐对枚举能够得到答案，但同一个查找会发生许多次；哈希表把已经见过的信息保存成一次查询。
3. 3优化维护候选人 candidate 与净票数 count:count 为 0 时把当前元素设为 candidate;当前元素等于 candidate 则 count+1,否则 count-1。多数元素和其他元素两两抵消后仍会剩下,所以扫描结束时的 candidate 就是答案。
4. 4证明count 始终等于当前 candidate 在「还没被抵消」的元素里的净票数;count 归零代表前面这一段已两两抵消干净。；多数元素出现次数 > ⌊n/2⌋,和其他所有元素一一抵消后仍有剩余。
5. 5复杂度时间 O(n)，空间 O(1)