Description
有一组数,很多很多个数,里面有一个数出现了超过一半次,请你把它找出来
Input
先是一个N (N<=1000000),然后接下来一行N个数,请一直处理到EOF.
Output
对每个Case,输出一行,这一行只含有一个在之前数列中出现超过一半次的数.
Sample Input
115 5 5 5 5 5 1 2 3 4 6
Sample Output
5
思路：1.可以排序，将所有数据存在一个数组中，并将其排序，取出其中间一个数就是出现频率超过一半的数，时间复杂度为O（nlogn);
2.在网上看到的一个新思路，因为这个数字出现超过半数，所以设置一个变量vote，即投票数，超半数的投票数减去其他数的出现次数肯定大于0，所以使用两个变量candidate和vote，分别代表候选人和票数，假设第一个输入的数字为首个候选者，
按如下方式投票和更换候选人：
若当前数与候选人一样，则把候选人的票数加1
若当前数与候选人不一样, 则把它的票数减1，如果减掉后票数小于0，则把候选人踢掉，用当前数作为新的候选人
最后剩下的候选人就是出现次数超过一半的数。
此思路引自：http://kenby.iteye.com/blog/1031114。
附上利用思路2写的代码：
#include
#include
int main(){
int N;
int candidate;
int ans;
int vote;
int temp;
while (scanf_s("%d", &N) != EOF){
if (N == 1 || N == 2){
scanf_s("%d", &ans);
}
else {
int i;
scanf_s("%d", &candidate);
vote = 1;
for (i = 0; i < N - 1; i++){
scanf_s("%d", &temp);
if (temp == candidate){
vote++;
}
else vote--;
if (vote == 0){
candidate = temp;
vote = 1;
}
}
ans = candidate;
}
printf("%d", ans);
}
}