浅析摩尔投票算法

·引入:

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

例如输入一个长度为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("该数字为:%dn", key);
flag = 1;
break;
}
}

if (flag==0)//不存在这样的数
{
printf("NOn");
}

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("该数字为:%dn", arr[mid]);
}

else
{
printf("NOn");
}
return 0;
}

·使用摩尔投票算法求解众数

一个投票场景:

想象一个场景:在n个人举行一次投票表决时,只有支持票(Y)和反对票(N)两种选择。众人举牌,将一个反对票和一个支持票看做一组,让他们放下牌子,重复此操作。

最后只会剩下两种情况:

1.有人举牌

则最后剩下的一方(Y/N)一定是票数较多的一方

2.无人举牌

说明两方票数相等,平票

摩尔投票算法

摩尔投票算法本质上就是重复将两个不同的数进行抵消,最后剩下的数一定是出现较多的。若最后剩下的数字个数为0,则不存在众数。

在实际操作中,可以想象两个虚拟的数组:一个数组(arr)用来维护待操作的数字,另一个数组用来进行具体的抵消操作(major)

浅析摩尔投票算法

一个举例

假设有这样一个数组 {1,2,3,2,2,2,5,4,2}

进行操作的步骤如下:

  1. 将arr中的第一个元素 "1" 放入major中。此时major中有一个元素 “1”,即 major={1}
  2. 因为此时只有 “1” 一个元素,没有可抵消的元素,所以将arr中的第二个元素 “2” 放入major。此时 major={1,2}
  3. 发现major中有两个不同的元素“1”和“2”,进行抵消操作,major中的元素清空。此时 major={ }
  4. 将arr中的元素 “3” 放入major。此时major中有一个元素 “3” ,即major={3}
  5. 因为此时只有 “3” 一个元素,没有可抵消的元素,所以将后面的元素 “2” 放入major。此时 major={3,2}
  6. 发现major中有两个不同的元素“3”和“2”,进行抵消操作,major中的元素清空。此时 major={ }
  7. 将元素arr中的 “2” 放入major。此时major中有一个元素 “2” ,即major={2}
  8. 因为此时只有 “2” 一个元素,没有可抵消的元素,所以将后面的元素 “2” 放入major。此时 major={2,2}
  9. 因为major中的元素 “2” 和 “2” 相等,无法抵消,所以将后面的元素 “ 5 ”放入major。此时major={2,2,5}
  10. 发现major中有两个不同的元素“2”和“5”,将一个2(无所谓哪一个)和5进行抵消。此时 major={2}
  11. 因为此时只有 “2” 一个元素,没有可抵消的元素,所以将后面的元素 “4” 放入major。此时 major={2,4}
  12. 发现major中有两个不同的元素“2”和“4”,进行抵消操作,major中的元素清空。此时 major={ }
  13. 将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("NOn");
}
else
{
printf("众数:%dn",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("NOn");
}

else//便利检验剩余的数(major)在数组中的出现次数
{
int count = 0;
for (int i = 0; i < sz; i++)
{
if (major == arr[i])
{
count++;
}
}
if(count>(sz/2))//验证通过
{
printf("该数字为:%dn",major);
}
else
{
printf("NOn");
}
}
}

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;
}

发表评论

相关文章