题目描述：
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
示例 1：
输入：[1,2,5,9,5,9,5,5,5] 输出：5
题源:https://leetcode-cn.com/problems/find-majority-element-lcci/
代码：该方法利用Hash，时间复杂度O(N)，但是空间复杂度也达到了O(N)，不满足
class Solution { public: int majorityElement(vector<int>& nums) { int l=nums.size(); int res=-1; map<int ,int> mp; for(int i=0;i<l;i++) { mp[nums[i]]++; if (mp[nums[i]]>l/2) {res=nums[i]; break;} } return res; } };
法二：要求空间是O（1）
所以只有下面这种方法是可行的：
class Solution { public: int majorityElement(vector<int>& nums) { /* // Hash方法 int l=nums.size(); int res=-1; map<int ,int> mp; for(int i=0;i<l;i++) { mp[nums[i]]++; if (mp[nums[i]]>l/2) {res=nums[i]; break;} } return res; */ // 法二，通过题解，投票机制 int l=nums.size(); int count=0; // 对num为众数的投票，如果num众数，则赞成>反对，即count>0 int num=0; // 假设现在众数为num for(int i=0;i<l;i++) { if(count==0) {num=nums[i]; count=1; continue;} if(nums[i]==num) count++; else count--; } count=0; for(int i=0;i<l;i++) if(nums[i]==num) count++; if (count>l/2) return num; else return -1; } };