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

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

【题目要求】给你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–；

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

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

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

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

关键代码如下所示：

#include

using namespace std;

int len;

void Find(int* a, int N)

{

char candidate;

int nTimes, i;

for(i=nTimes=0;i

{

if(nTimes==0) candidate=a[i],nTimes=1;

else

{

if(candidate==a[i]) nTimes++;

else nTimes--;

}

}

cout<

}

int main()

{

cin>>len;

int a[len];

for(int i=0;i>a[i];

Find(a,len);

system("pause");

return 0;

}

以上所述是给大家介绍的出现次数超过一半(50%)的数，希望对大家有所帮助，如果大家有任何疑问请给我MGtPTq留言，会及时回复大家的。在此也非常感谢大家对我们网站的支持！

{

if(nTimes==0) candidate=a[i],nTimes=1;

else

{

if(candidate==a[i]) nTimes++;

else nTimes--;

}

}

cout<

}

int main()

{

cin>>len;

int a[len];

for(int i=0;i>a[i];

Find(a,len);

system("pause");

return 0;

}

以上所述是给大家介绍的出现次数超过一半(50%)的数，希望对大家有所帮助，如果大家有任何疑问请给我MGtPTq留言，会及时回复大家的。在此也非常感谢大家对我们网站的支持！

}

int main()

{

cin>>len;

int a[len];

for(int i=0;i>a[i];

Find(a,len);

system("pause");

return 0;

}

以上所述是给大家介绍的出现次数超过一半(50%)的数，希望对大家有所帮助，如果大家有任何疑问请给我MGtPTq留言，会及时回复大家的。在此也非常感谢大家对我们网站的支持！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。