[Leetcode] Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Analysis:

An element m appearing more than n/2 times in the array means that the number of elements which is equal to m is greater than the ones which are different than m. So, if we increment the number by 1 for the m and decrement the number by for other different element, the element left which has count greater than 1 will be the majority element m. 

The code is very strait forward if you got the idea. The time complexity is O(n) since only one loop is needed. Pretty awesome, isn't it?

  int majorityElement(vector<int> &num) {
        int count = 0;
        int m;
        for(int i=0; i < num.size();i++)
        {
            if (count == 0)
            {
                m = num[i];
                count++;
            }
            else 
            {
                if (m != num[i])
                {
                    count--;
                }
                else
                {
                    count++;
                }
            }
        }
        return m;
    }