·引入：
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组{1, 2, 3, 2, 2, 2, 5, 4, 2}
由于数字2在数组中出现了五次，超过数组长度的一半，因此输出2
如果不存在则输出NO
分析一：计数器
一个数字出现的次数超过数组长度的一半，看到这些字眼最先想到的就是计算出数组中的每个数出现的次数times，如果times大于数组的长度的一半，则这个数就是所需要的数字；如果遍历数组未找到这样的数，则说明不存在这样的数。
#include<stdio.h>
int main()
{
int arr[50] = { 0 };
int sz = 0;
scanf("%d", &sz);
for (int i = 0; i < sz; i++)//输入数组中的元素
{
scanf("%d", &arr[i]);
}
int flag = 0;//假设不存在
for (int i = 0; i < sz-1; i++)//遍历数组
{
int key = arr[i];//标记基数
int count = 1;//注意count的初始值
for (int j = i+1; j < sz; j++)//向后搜寻数组元素
{
if (arr[j] == key)//搜寻到一个元素等于基数
{
count++;
}
}
//判断count是否符合条件
if (count>(sz / 2))//符合
{
printf("该数字为:%d\n", key);
flag = 1;
break;
}
}
if (flag==0)//不存在这样的数
{
printf("NO\n");
}
return 0;
}
该方法用到了嵌套循环，并非最优解。
分析二：排序
先将数组排序，然后取中间值，如果要求的数字存在，则一定是该中间值。若该中间值不符合条件，则要求的数字不存在。
void Bobble_sort(int arr[], int sz)
{
for (int i = 0; i < sz-1; i++)
{
for (int j = 0; j < sz-1-i; j++)
{
if (arr[j]>arr[j+1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
int main()
{
int arr[50] = { 0 };
int sz = 0;
scanf("%d", &sz);
for (int i = 0; i < sz; i++)
{
scanf("%d", &arr[i]);
}
//先排序，后判断
Bobble_sort(arr, sz);//进行冒泡排序
int left = 0;
int right = sz - 1;
int mid = (left + right) / 2;//取中间值下标
int count = 0;
for (int i = 0; i < sz; i++)//验证该中间值是否符合条件
{
if (arr[i]==arr[mid])
{
count++;
}
}
if (count>(sz/2))
{
printf("该数字为：%d\n", arr[mid]);
}
else
{
printf("NO\n");
}
return 0;
}
·使用摩尔投票算法求解众数
一个投票场景：
想象一个场景：在n个人举行一次投票表决时，只有支持票（Y）和反对票（N）两种选择。众人举牌，将一个反对票和一个支持票看做一组，让他们放下牌子，重复此操作。
最后只会剩下两种情况：
1.有人举牌
则最后剩下的一方（Y/N）一定是票数较多的一方
2.无人举牌
说明两方票数相等，平票
摩尔投票算法
摩尔投票算法本质上就是重复将两个不同的数进行抵消，最后剩下的数一定是出现较多的。若最后剩下的数字个数为0，则不存在众数。
在实际操作中，可以想象两个虚拟的数组：一个数组（arr）用来维护待操作的数字，另一个数组用来进行具体的抵消操作（major）。
一个举例
假设有这样一个数组 {1,2,3,2,2,2,5,4,2}
进行操作的步骤如下：
- 将arr中的第一个元素 "1" 放入major中。此时major中有一个元素 “1”，即 major={1}
- 因为此时只有 “1” 一个元素，没有可抵消的元素，所以将arr中的第二个元素 “2” 放入major。此时 major={1,2}
- 发现major中有两个不同的元素“1”和“2”，进行抵消操作,major中的元素清空。此时 major={ }
- 将arr中的元素 “3” 放入major。此时major中有一个元素 “3” ，即major={3}
- 因为此时只有 “3” 一个元素，没有可抵消的元素，所以将后面的元素 “2” 放入major。此时 major={3,2}
- 发现major中有两个不同的元素“3”和“2”，进行抵消操作,major中的元素清空。此时 major={ }
- 将元素arr中的 “2” 放入major。此时major中有一个元素 “2” ，即major={2}
- 因为此时只有 “2” 一个元素，没有可抵消的元素，所以将后面的元素 “2” 放入major。此时 major={2,2}
- 因为major中的元素 “2” 和 “2” 相等，无法抵消，所以将后面的元素 “ 5 ”放入major。此时major={2,2,5}
- 发现major中有两个不同的元素“2”和“5”，将一个2（无所谓哪一个）和5进行抵消。此时 major={2}
- 因为此时只有 “2” 一个元素，没有可抵消的元素，所以将后面的元素 “4” 放入major。此时 major={2,4}
- 发现major中有两个不同的元素“2”和“4”，进行抵消操作,major中的元素清空。此时 major={ }
- 将arr中的最后一个元素“2”放入major。此时major= { 2 }。因为数组arr中没有剩余其他元素，所以元素 “2” 为数组arr中出现最多的元素
通过这样一系列放入元素和进行抵消的操作，我们最后找出了数组arr中出现次数最多的元素，该元素为“2”。如果最后没有剩余元素，则说明数组arr无众数。使用该法能更高效地找出众数。
//摩尔投票算法求众数
void Moore(int arr[], int sz)
{
int major;//第一次进入，第一个元素与第一个元素比较，cnt++
int cnt = 0;
for (int i = 0; i < sz; i++)
{
if (cnt == 0)//若cnt为0，则给major重新赋值
{
major = arr[i];
}
if (major == arr[i])//两数相等，无法抵消
{
cnt++;
}
else//两数不等，进行抵消
{
cnt--;
}
}
if (cnt == 0)//数组中的数全部一一抵消，说明这样的数不存在
{
printf("NO\n");
}
else
{
printf("众数:%d\n",major);
}
}
int main()
{
int arr[] = { 1,2,1,3,1,1,2,1,5 };
//int arr[] = { 1,1,2,2,3,3,4,4,4 };
int sz = sizeof(arr) / sizeof(arr[0]);
Moore(arr, sz);
return 0;
}
·带回问题
同样的原理，可以用摩尔投票算法解决最初的问题。
但需要注意的是，使用该法进行计算，最后剩余的数字并不一定是所要求的数字。
例如有一个数组arr1中有元素 {1,1,2,2,3,3,4,4,4} 通过上面的分析可以得知最后剩余的数为 “4”，但4并不是该数组中出现超过一半的数字，因为该数组中并没有这样的数字，所以 “4” 并不是题解。
这就提醒我们，在用投票算法计算出一个数字之后，要进行最后的验证。如果验证通过，则输出该数；若验证不通过，则要求的数不存在。
#include<stdio.h>
void Moore(int arr[], int sz)
{
int major;//第一次进入，第一个元素与第一个元素比较，cnt++
int cnt = 0;
for (int i = 0; i < sz; i++)
{
if (cnt == 0)//若cnt为0，则给major重新赋值
{
major = arr[i];
}
if (major == arr[i])//两数相等，无法抵消
{
cnt++;
}
else//两数不等，进行抵消
{
cnt--;
}
}
if (cnt == 0)//数组中的数全部一一抵消，说明这样的数不存在
{
printf("NO\n");
}
else//便利检验剩余的数(major)在数组中的出现次数
{
int count = 0;
for (int i = 0; i < sz; i++)
{
if (major == arr[i])
{
count++;
}
}
if(count>(sz/2))//验证通过
{
printf("该数字为:%d\n",major);
}
else
{
printf("NO\n");
}
}
}
int main()
{
int arr[] = { 1,2,1,3,1,1,2,1,5 };
//int arr[] = { 1,1,2,2,3,3,4,4,4 };
int sz = sizeof(arr) / sizeof(arr[0]);
Moore(arr, sz);
return 0;
}
