LeetCode Q229: 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.

Solution:

For those who aren't familiar with Boyer-Moore Majority Vote algorithm, I found a great article (http://goo.gl/64Nams) that helps me to understand this fantastic algorithm!! Please check it out!

The essential concepts is you keep a counter for the majority number X. If you find a number Ythat is not X, the current counter should deduce 1. The reason is that if there is 5 X and 4 Y, there would be one (5-4) more X than Y. This could be explained as "4 X being paired out by 4 Y".

And since the requirement is finding the majority for more than ceiling of [n/3], the answer would be less than or equal to two numbers. So we can modify the algorithm to maintain two counters for two majorities.

	class Solution {
	public:
	vector<int> majorityElement(vector<int>& nums) {
	int num1, num2, count1=0, count2=0;
	for(int i=0; i<nums.size(); i++){
	int n=nums[i];
	if(n==num1){
	count1++; continue; }
	if(n==num2){
	count2++; continue; }
	if(count1==0){
	num1=n; count1=1; continue; }
	if(count2==0){
	num2=n; count2=1; continue; }
	count1--;
	count2--;
	}
	count1=0, count2=0;
	for(int i=0; i<nums.size(); i++){
	if(nums[i]==num1) count1++;
	if(nums[i]==num2) count2++;
	}
	vector<int> res;
	if(count1>nums.size()/3) res.push_back(num1);
	if(count2>nums.size()/3) res.push_back(num2);
	return res;
	}
	};

view raw Q229MajorityElementII.cpp hosted with ❤ by GitHub