[LintCode] Majority Number

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.

Example

Given [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

O(n) time and O(1) extra space

Moore’s Voting Algorithm:

class Solution {
public:
    int majorityNumber(vector<int> nums) {
        int len = nums.size();
        if(0 == len) return 0;
        int maj = nums[0], count = 1;
        for(int i=1;i<len;i++)
        {
            if(nums[i] == maj) count ++;
            else count --;
            if(0 == count) 
            {
                maj = nums[i];
                count = 1;
            }
        }
        return maj;
    }
};