算法训练营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/我看到题目的第一想法刚看到题目我第一反应是用一个计数器遍历数组统计每个元素出现的次数次数超过n/2的就是答案。但马上想到这种方法需要额外的空间来存次数不确定有没有更省空间的方法。因为题目说 “多数元素一定存在”我觉得它的出现次数超过一半会不会有什么更巧妙的办法不用统计所有数遇到的困难一开始只想到用哈希表 / 字典统计次数但不知道怎么实现O (1) 空间复杂度的解法。对摩尔投票法Boyer-Moore的原理理解不深一开始想不通为什么 “正负抵消” 后剩下的一定是多数元素。写代码时不知道怎么处理候选元素和计数的更新逻辑容易把条件写错。心得摩尔投票法的核心是 “正负抵消”多数元素出现次数大于一半所以即使和其他元素一一抵消最后剩下的也一定是它。这种方法只需要一次遍历时间复杂度 O (n)空间复杂度 O (1)比统计次数的方法更高效。算法题不只有 “暴力统计” 一种思路学会利用题目给的特殊条件比如 “多数元素一定存在”能找到更巧妙的解法。做题时要先思考优化空间理解算法背后的原理比会写代码更重要。