本文主要是介绍求一个数组的众数----------Majority Element169，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input: [3,2,3] Output: 3
Example 2:
Input: [2,2,1,1,1,2,2] Output: 2
public int majorityElement(int[] nums) {
// 用简单的HashMap去做
// HashMap<Integer,Integer> map=new HashMap<>();// int res = 0;
// for(int i=0;i<nums.length;i++)
// {
// int count=0;
// if(map.containsKey(nums[i]))
// map.put(nums[i], map.get(nums[i])+1);// else
// map.put(nums[i], 1);
// if(map.get(nums[i])>nums.length /2)
// {
// res=nums[i];
// break;
// }
// }
// return res;//用一种叫摩尔投票法 Moore Voting，需要O(n)的时间和O(1)的空间，比前一种方法更好。这种投票法先将第一个数字假设为众数，然后把计数器设为1，比较下一个数和此数是否相等，若相等则计数器加一，反之减一。然后看此时计数器的值，若为零，则将当前值设为候选众数。以此类推直到遍历完整个数组，当前候选众数即为该数组的众数。不仔细弄懂摩尔投票法的精髓的话，过一阵子还是会忘记的，首先要明确的是这个叼炸天的方法是有前提的，就是数组中一定要有众数的存在才能使用，下面我们来看本算法的思路，这是一种先假设候选者，然后再进行验证的算法。我们现将数组中的第一个数假设为众数，然后进行统计其出现的次数，如果遇到同样的数，则计数器自增1，否则计数器自减1，如果计数器减到了0，则更换当前数字为候选者。这是一个很巧妙的设定，也是本算法的精髓所在，为啥遇到不同的要计数器减1呢，为啥减到0了又要更换候选者呢？首先是有那个强大的前提存在，一定会有一个出现超过半数的数字存在，那么如果计数器减到0了话，说明目前不是候选者数字的个数已经跟候选者的出现个数相同了，那么这个候选者已经很weak，不一定能出现超过半数，我们选择更换当前的候选者。那有可能你会有疑问，那万一后面又大量的出现了之前的候选者怎么办，不需要担心，如果之前的候选者在后面大量出现的话，其又会重新变为候选者，直到最终验证成为正确的众数，佩服算法的提出者啊，代码如下：int res = 0, cnt = 0;for (int num : nums) {if (cnt == 0) {res = num; ++cnt;}else if (num == res) ++cnt;else --cnt;}return res;}
这篇关于求一个数组的众数----------Majority Element169的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
