出现（n+1）/2次的数 — 给n个数字，求至少出现（N+1）/2次的那个数字？_(n+1)/2

出现（n+1）/2次的数

• 题目：

give you N integers which include a SP number.The SP number appears at least (N+1)/2 times.
So can you find the SP number?

Input
The input contains several test cases. Each test case contains two lines.
The first line of input contains an odd integer N(1<=N<=999999) indicating the number of integers.
The second line contains the N integers(less than 10^6). The input is terminated by the end of file.

Output
For each test case, you have to output only one line which contains the SP number you have found.

Sample Input
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

Sample Output
3
5
1

---

• 分析思路

题目大意：给n个数字，求至少出现（N+1）/2次的那个数字。

---

1. 法一：对数字进行排序，之后进行扫描

代码一：
代码提交不通过，内存超限

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int n,t,cnt;
int a[10000010];

int main()
{
	while(cin>>n)
	{
		//sort(a,a+n);
    	memset(a,0,sizeof(a));
		for(int i=0;i<n;i++)
		{
			cin>>t;
			a[t]++;
		if(a[t]>=((n+1)/2))
		cnt=t;
	}
	cout<<cnt<<endl;
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2. 法二：利用map遍历，提交通过

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;

map<int,int> a;
int n,t,cnt;

int main()
{
	while(cin>>n)
	{
		a.clear();  //清除缓冲区字符
		int m=(n+1)/2;
		for(int i=1;i<=n;i++) {
			cin>>t;
			a[t]++;
			if(a[t]>=m) 
			cnt=t;
		}
		cout<<cnt<<endl;
	}
	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26