My linear solution (cpp).


  • 0
    E
    int majorityElement(vector<int> &num) 
    {
    	int index = 0;
    	int cnt = 0;
    	for (int i = 0; i < num.size(); i++)
    	{
    		if (num[i] == num[index])
    			cnt++;
    		else
    		{
    			cnt--;
    			if (cnt < 0)
    			{
    			    cnt = 0;
    			    index = i;
    			}
    		}
    	}
    	return num[index];
    }

  • 2
    D

    Yes, this algorithm is pretty cool, and all is credited to Boyer & More from University of Texas at Austin.
    You guys can take a look at the paper here.
    Below is the java implementation

    public class Solution {
        public int majorityElement(int[] num) {
            int vote = num[0];
            int count = 1;
            for(int i = 1; i < num.length; i++){
                if(count == 0) { vote = num[i]; count++; }
                else if(vote != num[i]) count--;
                else count++;
            }
            return vote;
        }
    }
    

  • 0
    G

    Thank you for pointing out the inventer of the algorithm.


Log in to reply
 

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