PAT (Advanced Level)-1041. Be Unique (20)

PAT (Advanced Level)-1041. Be Unique (20)

1041. Be Unique (20)

时间限制
100 ms
内存限制
65536 kB
代码长度限制 16000 B
判题程序 Standard
作者
CHEN, Yue


Being unique is so important to people on Mars that even their lottery is designed in a unique way. The rule of winning is simple: one bets on a number chosen from [1, 104]. The first one who bets on a unique number wins. For example, if there are 7 people betting on 5 31 5 88 67 88 17, then the second one who bets on 31 wins.


Input Specification:

Each input file contains one test case. Each case contains a line which begins with a positive integer N (<=105) and then followed by N bets. The numbers are separated by a space.

Output Specification:

For each test case, print the winning number in a line. If there is no winner, print “None” instead.

Sample Input 1:

7 5 31 5 88 67 88 17

Sample Output 1:

31

Sample Input 2:

5 888 666 666 888 888

Sample Output 2:

None

解读

遍历寻找重复。 用map的捆绑对应,可以将一个数字和它本身出现的次数绑定起来。减少搜索量。

完整代码

#include<iostream>
#include<vector>
#include<map>

int main()
{
	int N;
	std::cin >> N;
	std::vector<int> record_num;
	std::map<int, int> record_unique;
	for (int i = 0; i < N; i++)
	{
		int num;
		std::cin >> num;
		record_unique[num]++;
		record_num.push_back(num);
	}

	bool flag_num = false;
	int result;
	for (int i = 0; i < record_num.size(); i++)
	{
		if (record_unique[record_num[i]] == 1)
		{
			flag_num = true;
			result = record_num[i];
			break;
		}
	}

	if (flag_num == false)
	{
		std::cout << "None" << std::endl;
	}
	else
	{
		std::cout << result << std::endl;
	}
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注