Week12_t1
题目描述
给出n个数，zjm想找出出现至少(n+1)/2次的数， 现在需要你帮忙找出这个数是多少？
输入格式
本题包含多组数据：
每组数据包含两行。
第一行一个数字N(1<=N<=999999) ，保证N为奇数。
第二行为N个用空格隔开的整数。
数据以EOF结束。
输出格式
对于每一组数据，你需要输出你找到的唯一的数。
输入样例
5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1
输出样例
3
5
1
解题思路
时间复杂度要求并不高，直接暴力即可
#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;int a[100000];int main()
{ios::sync_with_stdio(false);cin.tie(0);int n;int maxone;//数值最大的while (cin >> n){memset(a, 0, sizeof a);maxone = 0;for (int i = 0, t; i < n; i++){cin >> t;a[t]++;maxone = max(maxone, t);}int judge = (n + 1) / 2;for (int i = 0; i <= maxone; i++){if (a[i] >= judge){cout << i << endl;break;}}}return 0;
}
Week12_t1
题目描述
给出n个数，zjm想找出出现至少(n+1)/2次的数， 现在需要你帮忙找出这个数是多少？
输入格式
本题包含多组数据：
每组数据包含两行。
第一行一个数字N(1<=N<=999999) ，保证N为奇数。
第二行为N个用空格隔开的整数。
数据以EOF结束。
输出格式
对于每一组数据，你需要输出你找到的唯一的数。
输入样例
5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1
输出样例
3
5
1
解题思路
时间复杂度要求并不高，直接暴力即可
#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;int a[100000];int main()
{ios::sync_with_stdio(false);cin.tie(0);int n;int maxone;//数值最大的while (cin >> n){memset(a, 0, sizeof a);maxone = 0;for (int i = 0, t; i < n; i++){cin >> t;a[t]++;maxone = max(maxone, t);}int judge = (n + 1) / 2;for (int i = 0; i <= maxone; i++){if (a[i] >= judge){cout << i << endl;break;}}}return 0;
}
发布评论