算法训练营Day12| LeetCode 169. 多数元素

题目链接：http:// https://leetcode.cn/problems/majority-element/

视频链接：http:// https://leetcode.cn/problems/majority-element/solutions/146074/duo-shu-yuan-su-by-leetcode-solution/

我看到题目的第一想法：

1. 刚看到题目，我第一反应是用一个计数器，遍历数组统计每个元素出现的次数，次数超过n/2的就是答案。
2. 但马上想到，这种方法需要额外的空间来存次数，不确定有没有更省空间的方法。
3. 因为题目说 “多数元素一定存在”，我觉得它的出现次数超过一半，会不会有什么更巧妙的办法，不用统计所有数？

遇到的困难：

1. 一开始只想到用哈希表 / 字典统计次数，但不知道怎么实现O (1) 空间复杂度的解法。
2. 对摩尔投票法（Boyer-Moore）的原理理解不深，一开始想不通为什么 “正负抵消” 后剩下的一定是多数元素。
3. 写代码时，不知道怎么处理候选元素和计数的更新逻辑，容易把条件写错。

心得：

1. 摩尔投票法的核心是 “正负抵消”：多数元素出现次数大于一半，所以即使和其他元素一一抵消，最后剩下的也一定是它。
2. 这种方法只需要一次遍历，时间复杂度 O (n)，空间复杂度 O (1)，比统计次数的方法更高效。
3. 算法题不只有 “暴力统计” 一种思路，学会利用题目给的特殊条件（比如 “多数元素一定存在”），能找到更巧妙的解法。
4. 做题时要先思考优化空间，理解算法背后的原理比会写代码更重要。