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

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

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

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {
 4         int maj = nums.at(0);
 5         for(int i = 0,c=0;i<nums.size();i++)
 6         {
 7             if(c == 0)
 8             {
 9                 maj = nums[i];c=1;
10             }
11             else
12             {
13                 nums[i] == maj ? c++:c--;
14             }
15         }
16         return maj;
17     }
18 };

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

Boyer-Moore Voting Algorithm

优质内容筛选与推荐>>
1、递推问题系列1--幂积序列
2、svn提交及更新时的常见问题
3、相机的对焦与合焦
4、课堂练习
5、Linux笔记（五） - 用户管理命令