问题描述：
给定一个序列，如果其中一个数出现的次数超过50%，请找出这个数.（默认都是存在众数的）
示例输入：
已知序列：[2,3,2,5,2,6,2,2]，找出主元素
示例输出：
2
题解：
方法一：
最简单的就是记录每个数字出现的次数，暴力解题。但是时间复杂度为O(n²)。
c语言代码：
#include
#include
#include
int main(void)
{
int n;
int a[101];
int count, max=0;
printf("数据个数:\n");
scanf("%d", &n);
int i, j, k = 0;
for (i = 1; i <= n; ++i) //循环存入数据
{
scanf("%d", &a[i]);
}
for (i = 1; i <= n; ++i) //遍历每一个数据
{
count = 0;
for (j = 1; j <= n; ++j)
{
if (a[i] == a[j] && i != j) //遇到相同的数据，计数器加1
{
count++;
}
}
if (count > max) //寻找有相同数据最多的数
{
max = count;
k = a[i];
}
}
printf("%d\n",k);
return 0;
} 方法二:
对所有的数进行递增排序，如果有一个数出现的次数超过50%，那么它一定位于n/2这个位置。时间复杂度为O(nlogn)。
/*对于堆，作向下调整，对内部变量h[101]作调整*/
int* siftdown2(int x, int num, int h[101])
{
int n = num, flag = 0;
int i, j;
j = x;
while (j <= n && flag == 0)
{
if (h[j] > h[2 * j] && 2 * j <= n)
{
i = 2 * j;
}
else
{
i = j;
}
if (h[i] > h[2 * j + 1] && 2 * j + 1 <= n)
{
i = 2 * j + 1;
}
if (i != j)
{
int t;
t = a[i];
a[i] = a[j];
a[j] = t;
j = i;
}
else
{
flag = 1;
}
}
return h;
}
int main(void)
{
int count = 1, max = 0;
printf("数据个数:\n");
scanf_s("%d", &n);
int i, k = 0;
for (i = 1; i <= n; ++i) //循环存入数据
{
scanf_s("%d", &a[i]);
}
siftup(n, a); //堆排序
int c = a[1];
int num = n;
for (i = 1; i <= n; ++i) //遍历每一个数据
{
a[1] = a[num];
--num;
siftdown2(1, num, a); //对于堆，作向下调整，对内部变量h[101]作调整
if (a[1] ==c) //找出下一个较小的数，与前一个比较是否相等
{
count++;
}
else
{
if (count > max) //寻找有相同数据最多的数
{
max = count;
k = a[i];
}
count = 1;
}
c = a[1];
}
printf("%d\n",k);
return 0;
}
方法三：
堆排序一个数组，排好后在主函数中给出第一个数，与第二个数比较，如相等count加1，如不相等，与max比较，更新max，最终找出多数元素
/*对于堆，作向上调整，对内部变量h[101]作调整*/
int* siftup(int n, int h[101])
{
int i = n, flag = 0, j;
while (i >= 1 && flag == 0)
{
if (h[i] < h[i / 2] && i >= 1)
{
j = i / 2;
int t;
t = a[i];
a[i] = a[j];
a[j] = t;
i = j;
}
else
{
flag = 1;
}
}
return h;
}
这个算法的时间复杂度是O(N+M)，空间复杂度也是O(N+M)。但是，如果序列中数的大小跨度比较大这个方法就不行了，空间开销非常大。那么看看下面的方法。
方法四：
也许你不知道，像这种序列的有一个特性，就是在原序列中去除两个不一样的数，原序列中出现超过50%的那个数，在取出的新序列中出现的次数也一定会超过50%。现在知道了，有没有想到解题的方法呢？
#include<stdio.h>
#include<stdlib.h>
int main()
{
int a[] = {3,1,1,2,3,1,3,3,3};
int i;
//初始化
int count = 1;
int temp = a[0];
for(i = 1; i < sizeof(a)/sizeof(int);i++)
{
if(count == 0)
{
temp = a[i];
count++;
}
else if(a[i] == temp)
count++;
else
count--;
}
printf("最多的数是:%d\n",temp);
system("pause");
return 0;
}Boyer-Moore 投票算法
如果我们把众数记为 +1+1，把其他数记为 -1−1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
Boyer-Moore 算法的本质和分治十分类似。 Boyer-Moore 算法的详细步骤：
我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
在遍历完成后，candidate 即为整个数组的众数。
举一个具体的例子，例如下面的这个数组：
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]在遍历到数组中的第一个元素以及每个在 | 之后的元素时，candidate 都会因为 count 的值变为 0 而发生改变。最后一次 candidate 的值从 5 变为 7，也就是这个数组中的众数。
Boyer-Moore 算法的正确性较难证明，这里给出一种较为详细的用例子辅助证明的思路，供读者参考：
首先我们根据算法步骤中对 count 的定义，可以发现：在对整个数组进行遍历的过程中，count 的值一定非负。这是因为如果 count 的值为 0，那么在这一轮遍历的开始时刻，我们会将 x 的值赋予 candidate 并在接下来的一步中将 count 的值增加 1。因此 count 的值在遍历的过程中一直保持非负。
那么 count 本身除了计数器之外，还有什么更深层次的意义呢？我们还是以数组
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]作为例子，首先写下它在每一步遍历时 candidate 和 count 的值：
nums: [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
candidate: 7 7 7 7 7 7 5 5 5 5 5 5 7 7 7 7
count: 1 2 1 2 1 0 1 0 1 2 1 0 1 2 3 4我们再定义一个变量 value，它和真正的众数 maj 绑定。在每一步遍历时，如果当前的数 x 和 maj 相等，那么 value 的值加 1，否则减 1。value 的实际意义即为：到当前的这一步遍历为止，众数出现的次数比非众数多出了多少次。我们将 value 的值也写在下方：
nums: [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
value: 1 2 1 2 1 0 -1 0 -1 -2 -1 0 1 2 3 4有没有发现什么？我们将 count 和 value 放在一起：
nums: [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
count: 1 2 1 2 1 0 1 0 1 2 1 0 1 2 3 4
value: 1 2 1 2 1 0 -1 0 -1 -2 -1 0 1 2 3 4发现在每一步遍历中，count 和 value 要么相等，要么互为相反数！并且在候选众数 candidate 就是 maj 时，它们相等，candidate 是其它的数时，它们互为相反数！
为什么会有这么奇妙的性质呢？这并不难证明：我们将候选众数 candidate 保持不变的连续的遍历称为「一段」。在同一段中，count 的值是根据 candidate == x 的判断进行加减的。那么如果 candidate 恰好为 maj，那么在这一段中，count 和 value 的变化是同步的；如果 candidate 不为 maj，那么在这一段中 count 和 value 的变化是相反的。因此就有了这样一个奇妙的性质。
这样以来，由于：
我们证明了 count 的值一直为非负，在最后一步遍历结束后也是如此；
由于 value 的值与真正的众数 maj 绑定，并且它表示「众数出现的次数比非众数多出了多少次」，那么在最后一步遍历结束后，value 的值为正数；
在最后一步遍历结束后，count 非负，value 为正数，所以它们不可能互为相反数，只可能相等，即 count == value。因此在最后「一段」中，count 的 value 的变化是同步的，也就是说，candidate 中存储的候选众数就是真正的众数 maj。
class Solution {
public:
int majorityElement(vector& nums) {
int candidate = -1;
int count = 0;
for (int num : nums) {
if (num == candidate)
++count;
else if (--count < 0) {
candidate = num;
count = 1;
}
}
return candidate;
}
}; 复杂度分析:
时间复杂度：O(n)O(n)。Boyer-Moore 算法只对数组进行了一次遍历。
空间复杂度：O(1)O(1)。Boyer-Moore 算法只需要常数级别的额外空间。
这个算法最初是在《啊哈！算法》看到的，通过最后一个方法可以将时间复杂度优化到O(n)，
