[169] 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.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

思路：每次从当前子序列中去处占据一半的数，那么众数的候选者只能是剩下一半的众数。当然这个数是候选者，最后仍然需要花费O(n)时间去验证，当然总的时间复杂度也是O(n).
solution

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int maj = nums.at(0);
        for(int i = 0,c=0;i<nums.size();i++)
        {
            if(c == 0)
            {
                maj = nums[i];c=1;
            }
            else
            {
                nums[i] == maj ? c++:c--;
            }
        }
        return maj;
    }
};

邓公书中的解法也就是solution中的方法6：

Boyer-Moore Voting Algorithm