首页 > 代码库 > 229. Majority Element II
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.
此题和major element的不同在于，由n/2 变成了n/3，那么看看再major element中用到的方法在这里还能不能继续用了：
1.hashmap，这个是可以的，代码如下：
<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px "Helvetica Neue"; color: #454545 }</style>public class Solution {
public List<Integer> majorityElement(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
List<Integer> res = new ArrayList<Integer>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
for(int key:map.keySet()){
System.out.println(key);
System.out.println(map.get(key));
if(map.get(key)>nums.length/3){
res.add(key);
}
}
return res;
}
}
2.moor voting algorithm
<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px "Helvetica Neue"; color: #454545 }</style>public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> res= new ArrayList<>();
if(nums.length==0) return res;
int major1 = nums[0];
int major2 = nums[0];
int count1 = 0;
int count2 = 0;
for(int i=0;i<nums.length;i++){
if(major1==nums[i]){
count1++;
}else if(major2==nums[i]){
count2++;
}else if(count1==0){
major1 = nums[i];
count1++;
}else if(count2==0){
major2= nums[i];
count2++;
}else{
count1--;
count2--;
}
}
count1=0;
count2=0;
for(int i=0;i<nums.length;i++){
if(major1==nums[i]) count1++;
else if(major2==nums[i]) count2++;
}
if(count1>nums.length/3) res.add(major1);
if(count2>nums.length/3) res.add(major2);
return res;
}
}
229. Majority Element II