1.题目描述
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2
提示：
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
2.题目分析
这道题目就是遍历+桶排就可以解决，在java中可以使用Map键值对来进行存储，然后通过遍历键值对来找到最大键值所对应的键就是要找的众数，代码实现如下：
static class Solution {
public Map<Integer,Integer> countNums(int[] nums){
Map<Integer,Integer> counts= new HashMap<Integer,Integer>();
for (int num : nums) {
if(!counts.containsKey(num)) {
counts.put(num, 1);
}
else {
counts.put(num, counts.get(num)+1);
}
}
return counts;
}
public int majorityElement(int[] nums) {
Map<Integer,Integer> counts = countNums(nums);
//定义存放最大值的键值对
Map.Entry<Integer, Integer> maxCouple = null;
for(Map.Entry<Integer,Integer> tempEntry : counts.entrySet()) {
if(maxCouple == null || tempEntry.getValue() > maxCouple.getValue()) {
maxCouple = tempEntry;
}
}
return maxCouple.getKey();
}3.提交结果
很显然，刚刚的那个只是常规解法，并没有做出太多思考和优化，现在我们需要来宠信审视该问题
4.进阶
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。既然空间复杂度为1，说明不能再通过键值对的存储方式，而是直接一边遍历一边存储最大值。对于这类众数问题，有个有趣的算法——摩尔投票法。
摩尔投票法的基础思想基于下述2个推论：
推论一： 若记 众数 的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的 票数和 >0 。
推论二： 若数组的前 a 个数字的 票数和 =0 ，则 数组剩余 (n−a) 个数字的 票数和一定仍 >0 ，即后 (n−a) 个数字的 众数仍为 x 。
看图片上的过程，因为众数的出现次数大于n/2，所以最后的众数的数量一定大于非众数的数量，所以最后的结果肯定>0,既然如此，我们就可以通过拆分子问题来解决，只要前n个子集的票数和为0，那么剩下的一个数就是众数，因为非众数已经和一个众数匹配相消为0。
只要在遍历的时候，当当前票数和为0，说明前面部分的众数和非众数的数量相等，可以直接舍弃，我们最后就只需要筛选只剩众数的时候。有些人可能会有疑惑，当前设定的众数并不是真正的众数，为什么不会影响得到正确的众数？这是因为这里的数只分为众数类和非众数类，前面的那些无论是不是真正的众数最后都会舍弃，因为真正的众数数量最多，所以无论哪一个非众数都能在众数的子集中找到匹配为0的数量，最后都会被真众数匹配完。
代码实现：
public int majorityElement(int[] nums) {
int x=0,votes=0;
for(int num:nums) {
if(votes == 0) {
x=num;
}
//等于当前设定众数为1，否则设为0
votes+=num==x?1:-1;
}
return x;
}
也是成功优化了时间。
5.总结
本次总结主要是基于摩尔投票法的应用，Boyer-Moore 投票算法（也称为摩尔投票法）是一种高效的算法，用于在数组中查找多数元素——即出现次数超过数组长度一半的元素。它的时间复杂度为 O(n)，空间复杂度为 O(1)，非常适合处理大数据集。在一个大型选举中，需要快速确定哪个候选人获得了超过一半的选票。假设每个选民投一票，并且我们知道存在一个获得超过一半选票的候选人。我们可以使用 Boyer-Moore 投票算法来高效地找到这个多数候选人。这种方法比传统的计数方法更节省时间和资源，特别是在选票数量非常大的情况下。往下推广，在线零售商希望了解哪些商品是顾客最常购买的，以便进行个性化推荐或促销活动。通过分析大量的购物篮数据，可以使用 Boyer-Moore 投票算法快速识别出最受欢迎的商品（即那些在多个购物篮中都出现的商品）。这有助于零售商更好地理解消费者偏好，从而优化库存管理和营销策略。可见该算法在大数据时代的实用度。
