找数

找数问题

问题描述

给出 n 个数，欲找出出现至少 (n + 1) / 2 次的数， 求这个数是多少？

Input

本题包含多组数据：每组数据包含两行。
第一行一个数字 N (1 ≤ N ≤ 999999) ，保证 N 为奇数。
第二行为 N 个用空格隔开的整数。
数据以 EOF 结束。

Output

对于每一组数据，输出找到的唯一的数。

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

Output: 
3
5
1

Limitation

Time limit      1000 ms
Memory limit    32767 kb

解题思路

排序，从头到尾扫一遍，计数，若次数不小于(n + 1) / 2，则找出了这个数。

源代码

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

const int maxN = 1000010;
int arr[maxN];

int solve(int n) {
	int cnt = (n + 1) / 2;

	int a = arr[0];
	int cnt1 = 0;
	
	for (int i = 0; i < n; i++) {
		if (arr[i] == a)
			cnt1++;
		else {
			if (cnt1 >= cnt)
				break;
			a = arr[i];
			cnt1 = 0;
		}
	}
	return a;
}

int main() {
	int n;
	while (!(cin >> n).eof()) {
		for (int i = 0; i < n; i++)
			cin >> arr[i];
		sort(arr, arr + n);
		int res = solve(n);
		cout << res << endl;
	}
	return 0;
}