试题 算法提高 JOE的众数（蓝桥杯）

试题 算法提高 JOE的众数

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

　　JOE有一个长度为n的数组A，已知其中至少有一半以上的元素相同，现在JOE想知道数组的众数。

输入格式

　　第一行，一个数n。
　　第二行，n个正整数，表示A数组。

输出格式

　　一个数，表示这n个数的众数。

样例输入

5
1 1 2 1 2

样例输出

1

数据规模和约定

　　30% n <= 10^4，数值 <= 10^8
　　60% n <= 10^7，数值 <= 10^6
　　100% n <= 10^7，数值 <= 10^8

简直，深痛恶绝的题目，摩尔投票法都过不了，简直恶心；

附上O（n）但是只能拿六十分的摩尔投票法；

还有一个满分 哈希表（map）写法；

最后发现，用map 查找效率为以2为底N的对数的效率即 log2（N）查找；

找到第一个出现大于 1/2 * n 个数量的元素，就是最终答案；

就一句话，sb题目！

最后还是拼阳寿，玩概率过的；

如果map不玩概率，就过不了，O（n）都过不了，还要我怎么办？

#include <bits/stdc++.h>
using namespace std;
int nums[10000000];
int main() {
	int n;
	scanf("%d",&n);
	for (int i=0; i<n; i++) {
		scanf("%d",&nums[i]);
	}
	int major, counts = 0;
	for (int i = 0; i < n; i++) {
		if (counts == 0) {
			major = nums[i];
			counts = 1;
		} else counts += (nums[i] == major) ? 1 : -1;
	}
	printf("%d",major);
	return 0;
}
//摩尔投票法

#include<iostream>
#include<map>
using namespace std;
map <int, int>mp;
int n,t,max1 = 0,s;
int main() {
	scanf("%d",&n);
	for (int i = 0; i < n/100; i++) {
		scanf("%d", &t);
		mp[t]++;
		if (mp[t] > max1) {
			max1 = mp[t];
			s = t;
		}	
	}
	printf("%d",s);
	return 0;
}
//map 阳寿法，就是强行
只读入百分之一的数据，然后过的，
简直不讲道理
要是数据读入 百分之百，就过不了；

最后效率挺高的，这些蓝桥杯的测试点大概就跑了31ms，

如果是读入一半的数据过不了；

读入百分之二十五的数据就800多ms；

最后总结，没用的训练，就是拼概率，题目辣鸡；

最快的效率O（n）我还要减少读入数据才能过，真是无语！