题目描述 给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。 示例 1: 输入: [3,2,3] 输出: [3] 示例 2: 输入: [1,1,1,3,3,2,2,2] 输出: [1,2] https://leetcode-cn.com/problems/majority-element-ii/ 解法1 使用Map统计每种数字出现的频率，当发现元素e出现当频率大于⌊ n/3 ⌋时，将其加入到结果列表中，当扫描完数组后返回结果列表。时间复杂度与空间复杂度均为O(n)。 解法2 解法2使用169题的方法，也就是Boyer–Moore majority vote algorithm。我们首先分析下，在数组中出现频率超过⌊ n/3 ⌋最多能有几种元素。容易想到，最多我们只能找到两个元素，它的出现频率大于⌊ n/3 ⌋（如果存在3个，则3个元素频率均为n/3）。 我们还是使用Boyer-Moore算法，创建4个变量counter1、counter2、num1、num2。遍历每个元素e，如果counter1为0，则将元素e赋给num1，且将counter1置为1；如果counter2为0，则将元素e赋给num2，且将counter2置为1；如果e == num1，则counter1自增1；如果e == num2，则counter2自增1；否则（e!=num1且e!=num2），counter1与counter2自减1. 全部代码如下，需要注意的是需要将判断e == num1/2放在if(counter1/2 == 0)之前，否则出现两个相同的元素，将会分别使用counter1与counter2统计，逻辑就不正确了。

题目描述 给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2] 输出: 2 https://leetcode-cn.com/problems/majority-element/ 解法1 使用Map统计每个数出现的频率，当发现元素e出现的频率超过⌊ n/2 ⌋时，返回元素e。时间复杂度与空间复杂度均为O(n) 解法2 对数组排序，然后返回中间元素。因为元素e超过了⌊ n/2 ⌋，那么排序后数组的中间位置已定是元素e。时间复杂度O(nlogn)，空间复杂度O(1) 解法3 该方法被称为Boyer-Moore majority vote algorithm。设置变量majority与counter。依次遍历每个元素e，当计数器counter为0时，将e赋给majority，设置counter为1；此后的循环，当发现e==majority时，counter自增1；当发现e!=majority时，counter自减1。 该算法执行完毕时，若存在频率高于⌊ n/2 ⌋的元素，则majority存放的就是答案。如果不存在频率高于⌊ n/2 ⌋的元素，则该算法并不能识别出这种情况。需要再次扫描统计majority出现的频率。 但是本题给定了说明一定存在众数，我们就只需要扫描一次然后返回majority变量即可。全部代码如下。