本文主要是介绍leetcode 229:Majority Element II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
题目分析：这道题跟Majority Element类似，我想到摩尔投票。
摩尔投票的原理：
首先我们注意到这样一个现象： 在任何数组中，出现次数大于该数组长度一半的值只能有一个。
通过数学知识，我们可以证明它的正确性，但是这并不在我们这篇博客里涉及。
摩尔投票法的基本思想很简单，在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。这样不断的删除直到无法再进行投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的一半。如果只存在一种元素，那么这个元素则可能为目标元素。
那么有没有可能出现最后有两种或两种以上元素呢？根据定义，这是不可能的，因为如果出现这种情况，则代表我们可以继续一轮投票。因此，最终只能是剩下零个或一个元素。
在算法执行过程中，我们使用常量空间实时记录一个候选元素c以及其出现次数f(c)，c即为当前阶段出现次数超过半数的元素。根据这样的定义，我们也可以将摩尔投票法看作是一种动态规划算法。
程序开始之前，元素c为空，f(c)=0。遍历数组A：
* 如果f(c)为0，表示截至到当前子数组，并没有候选元素。也就是说之前的遍历过程中并没有找到超过半数的元素。那么，如果超过半数的元素c存在，那么c在剩下的子数组中，出现次数也一定超过半数。因此我们可以将原始问题转化为它的子问题。此时c赋值为当前元素, 同时f(c)=1。
* 如果当前元素A[i] == c, 那么f(c) += 1。(没有找到不同元素，只需要把相同元素累计起来)
* 如果当前元素A[i] != c，那么f(c) -= 1 (相当于删除1个c)，不对A[i]做任何处理(相当于删除A[i])
如果遍历结束之后，f(c)不为0，则找到可能元素。
再次遍历一遍数组，记录c真正出现的次数，从而验证c是否真的出现了超过半数。上述算法的时间复杂度为O(n)，而由于并不需要真的删除数组元素，我们也并不需要额外的空间来保存原始数组，空间复杂度为O(1)。
对于此题，我们可以考虑下面的东西：
1. 超过1/3的值不超过两个
2. 可以扫描两轮，第一轮需要找到潜在对象，设定两个潜在对象，如果是对象，对应数值增加，如果count=0，更新，否则count--.
第二轮找到潜在对象对应的个数。
3.需要对数值等于0特殊处理
具体代码如下：
public List<Integer> majorityElement(int[] nums) {List<Integer> res=new ArrayList<Integer>();int n1=0;int n2=0;int cn1=0;int cn2=0;int len=nums.length;for(int i=0;i<len;i++ ){if(nums[i]==n1){cn1++;}else if(nums[i]==n2){cn2++;}else if(cn1==0){n1=nums[i];cn1++;}else if(cn2==0){n2=nums[i];cn2++;}else{cn1--;cn2--;}}if(cn2==0&&len>0){n2=0;}cn1=0;cn2=0;int cn0=0;for(int i=0;i<len;i++){if(nums[i]==n1)cn1++;else if(nums[i]==n2)cn2++;else if(nums[i]==0)cn0++;}if(cn1>(len/3)){res.add(n1);}if(cn2>(len/3)){res.add(n2);}if(cn0>(len/3)&&n1!=0&&n2!=0){res.add(0);}return res;}这篇关于leetcode 229:Majority Element II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
