题目
思路1（排序）
因为题目说一定会存在超过数组长度一半的一个数字，所以我们将数组排序后，位于length/2位置的一定是众数
代码
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
复杂度分析
时间复杂度：\(O(NlogN)\)
空间复杂度：\(O(1)\)
思路2（哈希表）
遍历一遍数组，将数组的值作为键，出现的次数作为值，存放到哈希表中
遍历哈希表，找到出现次数最多的那一个键值对就是我们要的众数
代码
class Solution {
public int majorityElement(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int n : nums) {
map.put(n, map.getOrDefault(n, 0) + 1);
}
int max = 0;
int res = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (max < entry.getValue()) {
max = entry.getValue();
res = entry.getKey();
}
}
return res;
}
}
复杂度分析
时间复杂度：\(O(N)\)
空间复杂度：\(O(N)\)
思路3（分治）
将数组从中间开始不断分成两份，直到只剩下一个元素时候开始返回
如果left和right出现的频率一样，直接返回
计算left和right在lo～hi范围内出现的频率，将高频率的返回
为什么可以用这个方法？比如有[1, 2, 3, 2, 2, 2, 5, 4, 2]，共有9个元素，共会被分成5份(每份一个或者两个元素)，然后从每份中再获取一个值，共获取5个值，又因为众数的个数要大于数组的长度，所以，众数一定会至少被选中一个，只要被选中一个，那么我们的countInRange函数会根据范围帮我们计算出最多出现的元素个数即众数
代码
class Solution {
public int majorityElement(int[] nums) {
return majorityElementRec(nums, 0, nums.length-1);
}
public int majorityElementRec(int[] nums, int lo, int hi) {
// 如果只有一个元素，那么直接返回
if (lo == hi) {
return nums[lo];
}
// 获取中间值
int mid = lo + (hi - lo) / 2;
// 递归左边和右边，直到剩下一个元素
int left = majorityElementRec(nums, lo, mid);
int right = majorityElementRec(nums, mid+1, hi);
// 相等只需要返回一个
if (left == right) {
return left;
}
// 计算left和right在lo～hi范围中的出现的次数
int leftCount = countInRange(nums, left, lo, hi);
int rightCount = countInRange(nums, right, lo, hi);
// 返回出现次数多的数
return leftCount > rightCount ? left : right;
}
// 统计目标数字在指定范围出现的次数
public int countInRange(int[] nums, int target, int lo, int hi) {
int count = 0;
for (int i = lo; i <= hi; i++) {
if (nums[i] == target) {
count++;
}
}
return count;
}
}
复杂度分析
时间复杂度：\(O(NlogN)\)
空间复杂度：\(O(logN)\)，递归过程中使用了额外的栈空间
思路4（摩尔投票法）
众数记为+1，把其他数记为-1，将它们全部加起来，和最终会大于0
假设众数记为res，票数记为votes，假设有这么一个数组：[1, 2, 3, 2, 2, 2, 5, 4, 2]，使用摩尔投票法的过程如下：
i=0时：因为当前票数为0，所以将1赋值给res，同时票数也加一。此时res=1 votes=1
i=1时：2不等于1，所以票数要减1，此时res=1 votes=0
i=2时：因为票数为0，所以众数res要指向当前的3，然后票数加一，此时res=3 votes=1
i=3时：2不等于3，所以票数要减1，此时res=3 votes=0
i=4时：因为票数为0，所以众数res要指向当前的2，然后票数加一，此时res=2 votes=1
i=5时：由于2=2，所以票数加一，此时res=2 votes=2
i=6时：5不等于2，所以票数要减1，此时res=2 votes=1
i=7时：4不等于2，所以票数要减1，此时res=2 votes=0
i=8时：因为票数为0，所以众数res要指向当前的2，然后票数加一，此时res=2 votes=1
最后就直接输出res即为众数
代码
class Solution {
public int majorityElement(int[] nums) {
// 代表结果的众数
int res = nums[0];
// 统计票数
int votes = 0;
for (int i = 0; i < nums.length; i++) {
// 刚开始是0票，所以把数组的第一个元素作为众数
// 如果以后的循环votes票数被抵消掉了为0，那么下一个元素就作为众数
if (votes == 0) {
res = nums[i];
}
// 和当前众数相同的，那么票数就加1
if (res == nums[i]) {
votes++;
} else {
// 如果和当前票数不同，票数就被抵消掉了一个
votes--;
}
}
return res;
}
}
复杂度分析
时间复杂度：\(O(N)\)
空间复杂度：\(O(1)\)
![2021-12-30：分裂问题。 一个数n，可以分裂成一个数组[n/2, n%2, n/2]， 这个数组中哪个数不是1或者0，就继续分裂下去。 比如 n = 5，一开始分裂成[2, 1, 2]， [2](https://www.kunjuke.com/file/css/thumb/9.jpg/280-180.jpg)
