欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

出现次数超过一半(50%)的数

程序员文章站 2024-03-13 10:26:39
【题目要求】给你n个数与n。现在需要你在o(n)的时间内,o(1)的空间内找出出现次数超过50%的数。 【开始胡扯】一开始我看到这道题瞬间蒙蔽(tot)/~~~(。﹏...

【题目要求】给你n个数与n。现在需要你在o(n)的时间内,o(1)的空间内找出出现次数超过50%的数。

【开始胡扯】一开始我看到这道题瞬间蒙蔽(tot)/~~~(。﹏。*),要是只有o(n)的时间这一条要求,就可以用哈希瞬间解决(也就是用空间换时间),对于o(1)的空间好像很难解决。

【思路一】双重循环,这是解决这道题效率最低的方法了,也就是对每个数都计算它出现的次数,时间复杂度 o(n^2) 直接out。

【思路二】先排序,让相近的数字排在一起,然后从第一个数开始遍历,现在给一个例子,如:1000012,现在进行排序:0000112,从0开始,设定一个计数器t=0,现在有4个0,则t=4,发现超过了半数,输出0。这个方法就是上一个方法的优化版,out。

【思路三】就是以空间换时间,哈希的思想,使一个一维数组有两个含义。比如a[x]=y代表x这个数出现了y次,这个方法时间复杂度是o(n),但是空间实在是……不说了(*  ̄︿ ̄) out

【思路四】先算出概率,选出这些数中最有可能符合要求的几个数,再随机抽取几个。这……还是算了吧。

【思路五】今天的主题,就是所谓的mjrty算法,也叫多数投票算法,主要思路如下:(这个算法时间复杂度o(n)!空间上不需要额外的储存,所以空间复杂度是o(1)!!!!!!)

如果count==0,则将vote的值设置为数组的当前元素,将count赋值为1;

否则,如果vote和现在数组元素值相同,则count++,反之count–;

重复上述两步,直到扫描完数组。

count赋值为0,再次从头扫描数组,如果数组元素值与vote的值相同则count++,直到扫描完数组为止。

如果此时count的值大于等于n/2,则返回vote的值,反之则返回-1;

以下是代码实现,由于题目保证结果一定存在,所以我们省去了最后一步的检查验证。

关键代码如下所示:

#include<iostream>
using namespace std;
int len; 
void find(int* a, int n) 
{
char candidate;
int ntimes, i;
for(i=ntimes=0;i<n;i++)
{
if(ntimes==0) candidate=a[i],ntimes=1;
else
{
if(candidate==a[i]) ntimes++;
else ntimes--;
}
}
cout<<candidate; 
}
int main()
{
cin>>len;
int a[len];
for(int i=0;i<n;i++) cin>>a[i];
find(a,len);
system("pause");
return 0;
} 

以上所述是小编给大家介绍的出现次数超过一半(50%)的数,希望对大家有所帮助