# Boyer-Moore method Java Implementation.

• ``````public class Solution{
public List<Integer> majorityElement(int[] nums){
List<Integer> rst = new ArrayList<Integer>();
if(nums == null || nums.length == 0) return rst;
int count1 = 0, count2 = 0, candidate1 = 0, candidate2 = 1;
for(int num : nums){
if(num == candidate1) count1++;
else if(num == candidate2) count2++;
else if(count1 == 0){
candidate1 = num;
count1 = 1;
}
else if(count2 == 0){
candidate2 = num;
count2 = 1;
}
else{
count1--;
count2--;
}
}
count1 = 0; count2 = 0;
for(int num : nums){
if(num == candidate1) count1+=2;
else count1--;
if(num == candidate2) count2 += 2;
else count2--;
}
if(count1 > 0) rst.add(candidate1);
if(count2 > 0) rst.add(candidate2);
return rst;
}
}``````

• dsrwwe

ew
wr
wq
we

wqrwq
rwq
r
qr
qw
rwq

q
rq
qew
rewq
rewqr
w
rewq
we
rwq

• Cool implementation, but this won't return multiple numbers much less numbers which pass a threshold of floor(N/3)

• cool inspiration, thank you!

• Edited my answer to make it right, thank you

• !!!!!!!!do not work for [0,0,0]

• Almost identical code in C++. Moore algorithm. 2N time complexity.

``````vector<int> majorityElement(vector<int>& nums) {
int a, b, cnta(0), cntb(0);
for(auto i:nums) {
if(cnta && i == a) cnta++;
else if(cntb && i == b) cntb++;
else if(!cnta) {
cnta = 1;
a = i;
}
else if(!cntb) {
cntb = 1;
b = i;
}
else {
cnta--;
cntb--;
}
}
if(!cnta && !cntb) return {};
cnta = cntb = 0;
for(auto i:nums) {
if(i == a) cnta++;
if(i == b) cntb++;
}
vector<int> ret;
if(cnta > nums.size() / 3) ret.push_back(a);
if(b!= a && cntb > nums.size() / 3) ret.push_back(b);
return ret;
}``````

• this is an accurate representation of my frustration right now!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.