今天在leetcode 上看见一个题：
如果数组中多一半的数都是同一个，则称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。
一开始想用map（虽然也不太会）
其实这个题，有个限定条件＂多于一半＂，所以就会有一种感觉＂map用可惜了＂，一定有更好的算法满足这个条件啊．
当然这个题还有别的思路：数组计数和排序找中间值（排序后出现次数大于一半的肯定在中间）
然后看dl题解，发现有个东西叫：摩尔投票．
所以我们来看一下摩尔投票
摩尔投票法基于这样一个事实，
当一个数的重复次数超过数组长度的一半，每次将两个不相同的数删除，最终剩下的就是要找的数。
大体思路：
找一个计数器，设基准数，挨个遍历，相同则计数器加一，不同则减一（如果主要元素一定存在的话，计数器小于零就可以重置了）
但没法满足不存在就返回-1
好办，用摩尔投票找出那个数，然后遍历数组看看是不是就行．
1 int majorityElement(vector<int>& nums) 2 { 3 //投票算法 4 int len = nums.size(); 5 if (len == 0) return -1;//边缘数据也要把握好 6 7 int tmp = nums[0], cnt = 1; 8 for (int i = 1; i < len; i++) 9 { 10 if (nums[i] == tmp) cnt++; 11 else cnt--; 12 13 if (cnt == 0) tmp = nums[i], cnt = 1; 14 } 15 16 //验证tmp是不是超过一半 17 cnt = 0; 18 for (auto n : nums) 19 if (n == tmp) cnt++; 20 return cnt > len / 2 ? tmp : -1; 21 }
原文：https://www.cnblogs.com/zhmlzhml/p/12639432.html