Lintcode: Majority Number

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

Have you met this question in a real interview?

Yes

Example

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

Challenge

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

Tags Expand 

Greedy Enumeration LintCode Copyright

My leetcode hashmap solution

Greedy method:(Moore voting algorithm)

http://leetcodesolution.blogspot.com/2015/01/leetcode-majority-element.html  //c++ solution

http://bookshadow.com/weblog/2014/12/22/leetcode-majority-element/  //provide several solutions

Just keep recording one element and times appeared, and iterate the array. If current element equals to the recorded one, count plus 1; If not, count -1 until count == 0, then change the recorded element to current one.

The key is that the majority element occurs more than half times. Even in worst case, the recorded time will be at least one.

Time; O(n)

Space: O(1)

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: The majority number
     */
    int majorityNumber(vector<int> nums) {
        // write your code here
        int major = -1;
        int count = 0;
        for(int i = 0; i < nums.size(); i++){
            if(!count) {
                major = nums[i];
                count++;
            }
            else if(major == nums[i]){
              count++;
              if(count > nums.size() / 2) return major; //just optimization, not necessary
            }
            else {
                count--;
            }
        }
        return major;
    }
};