Majority Element

LeetCode #169

Description:

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.

Example:

Note

Idea:

Moore's voting algorithm. 但必须是有majority element，如果没有element多于一半，则出来的结果不是最多的element。

Code:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count=1;
        int major_ind=0;
        for(int i=1; i<nums.size(); ++i){
            if(nums[major_ind]==nums[i]){
                count++;
            }
            else{
                count--;
            }

            // select new majority element:
            if(count==0){ 
                count=1;
                major_ind=i;
            }
        }

        return nums[major_ind];

    }
};