229.求众数
题目：给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
测试用例：
输入：[3,2,3]
输出：[3]
题目分析：这是一个摩尔投票问题。所谓摩尔投票，就像一场大仗，分为两个阵营，若两个阵营都有活着的士兵，则互相厮杀，直至某个阵营完全破灭。而该题目，对于任意一个数组，假设有m个数出现恰好n/3次，那么还剩n-nm/3=(1-m/3)n>=0，那么m<=3，由于要超过n/3次，因此m<3，即m最大为2，也就是任意一个数组，最多只有2个数出现超过n/3次。因此，假设两个变量A和B，并且对这两个变量计数，逐个扫描数组，当A还没有赋值时，则把当前值赋给A，并且countA加1，往后扫描，若当前值不为A并且B还没有赋值时，同理把当前值赋给A，并且countB加1，往后扫描；若当前值与A相等，并且countA不为0（避免恰好当前值为初始值），那么A所在阵营个数+1；同理B；若当前值不与AB相等，那么相当于AB阵营都阵死一个。最终根据countA和countB是否为0，判断当前AB是否有效。而此时得到的AB仅为出现次数最多和次多的，并且countA和countB并不是AB在数组中出现的次数，因此还需要循环一次，求出AB出现的次数，并判断是否大与n/3。
代码：
class Solution {
public:
vector majorityElement(vector& nums) {
int A = 0;
int B = 0;//存放出现次数最多的数
int countA = 0;
int countB = 0;
vector num;
if(nums.size()<1 || nums.size()>5e4)
{
return num;
}
else
{
for (int i = 0;i0? true:false;
bool Bm = countB>0? true:false;//表示此时的AB是否有值，避免恰好为0的情况
countA = 0;
countB = 0;
for (int i = 0;inums.size()/3)
{
num.push_back(B);
}
if(countA>nums.size()/3)
{
num.push_back(A);
}
return num;
}
};
执行用时：16 ms, 在所有 C++ 提交中击败了33.82%的用户
内存消耗：15.4 MB, 在所有 C++ 提交中击败了54.37%的用户
相似题目：169.多数元素
题目：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
题目分析：最多只有一个元素，设为most，并计数。
代码：
在class Solution {
public:
int majorityElement(vector& nums) {
int most = 0;
int count = 0;
for(int i = 0;inums.size()/2)
{
return most;
}
else
{
return false;
}
}
};
执行用时：20 ms, 在所有 C++ 提交中击败了46.82%的用户
内存消耗：19.1 MB, 在所有 C++ 提交中击败了64.07%的用户
