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那样直接sort然后取巧就可以解决了。
不过还是比较简单的，老老实实地先sort之后挨着挨着count即可。
只是注意这里的special case(count>(nums.length/3)一定要放在for loop后面噢。
关于为啥请直接思考length=2的情况就懂了哈哈。
代码如下。~
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> result=new ArrayList<Integer>();
if(nums.length==0){
return result;
}
Arrays.sort(nums);
int count=1;
int temp=nums[0];
for(int i=1;i<nums.length;i++){
if(nums[i]==temp){
count++;
}else if(count>(nums.length/3)){
result.add(temp);
temp=nums[i];
count=1;
}else{
temp=nums[i];
count=1;
}
}
if(count>(nums.length/3)){
result.add(temp);
}
return result;
}
}
[LeetCode] Majority Element II
原文：http://www.cnblogs.com/orangeme404/p/4744603.html