首页 > 代码库 > Timus 1510. Order 找到出现次数过半的数
Timus 1510. Order 找到出现次数过半的数
A New Russian Kolyan likes two things: money and order. Kolyan has lots of money, but there is no order in it. One beautiful morning Kolyan understood that he couldn‘t stand this any longer and decided to establish order in his money. He told his faithful mates to fetch the money from an underground depository, and soon his big room was filled up with red, green, and blue banknotes. Kolyan looked with disgust at this terrible mess. Now he wants to leave in his depository only banknotes of the same value and to give the rest of the money to the poor. He knows exactly that more than half banknotes have the same value. But in this mess it is impossible to understand which banknote is the most common.
Input
The first line contains the number of Kolyan‘s banknotes N (1 ≤ N ≤ 500000). In the next N lines, the values K of these banknotes are given (0 ≤ K ≤ 109). More than half of them are the same.
Output
Output the most common value.
Sample
| input | output |
|---|---|
5 3 3 2 2 3 | 3 |
又是一个新的算法，原来可以这样查找的。
我的一句话理解的思想：
计算可以抵消的数量，那么如果一个数出现的次数超过半那么最终这个数肯定不会被抵消完。
这个思想叫 Moore’s Voting Algorithm
有了这个思想武器之后，程序就可以写的很简单，可以很清楚看到怎么实现的，
参考资料可以看：
http://www.geeksforgeeks.org/majority-element/
#include <iostream>
using namespace std;
void main()
{
int n = 0, a = 0, majority = 0, c = 1;
cin>>n>>majority;
while (--n)
{
cin>>a;
if (majority == a) c++;
else c--;
if (0 == c)
{
majority = a;
c = 1;
}
}
cout<<majority;
}Timus 1510. Order 找到出现次数过半的数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。