·引入:
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
例如输入一个长度为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;
}