剑指 Offer 39. 数组中出现次数超过一半的数字
思路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=1i=1时：2不等于1，所以票数要减1，此时res=1 votes=0i=2时：因为票数为0，所以众数res要指向当前的3，然后票数加一，此时res=3 votes=1i=3时：2不等于3，所以票数要减1，此时res=3 votes=0i=4时：因为票数为0，所以众数res要指向当前的2，然后票数加一，此时res=2 votes=1i=5时：由于2=2，所以票数加一，此时res=2 votes=2i=6时：5不等于2，所以票数要减1，此时res=2 votes=1i=7时：4不等于2，所以票数要减1，此时res=2 votes=0i=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)
作者：林泽良
出处：https://www.cnblogs.com/linzeliang1222/p/15431523.html