P6365 [传智杯 #2 初赛] 众数出现的次数（C++）

原题链接：P6365 [传智杯 #2 初赛] 众数出现的次数 - 洛谷

题目描述

传智专修学员的课堂上，为了活跃气氛，并巩固位运算的知识，同学们玩起了一个游戏。

班级里有 n(n≤106) 名同学，每位同学都获得了两张卡，红卡或者黑卡。每张卡上都有一个不超过 109 的非负整数。第 i 位同学手里红卡数字是 ai​ ，黑卡数字是 bi​。

现在需要每位同学出牌。每位同学可以直接将红卡上的数字打出，或者将自己的红卡上的数字和自己黑卡数字进行按位异或操作后的结果打出。最后老师会收集所有同学打出的数字。

这些数字中出现次数最多的数字是众数。在所有同学合作的最优策略下，我们希望众数对应数字出现的次数尽可能多。请问出现次数最多的数字是多少呢？

输入格式

第一行，一个正整数 n。

接下来 n 行，其中第 i 行时非负整数 ai​,bi​ 代表第 i 名同学手上红卡和黑卡的数字。

输出格式

一个整数，表示答案。如果有多个解，请输出最小的那个。

输入输出样例

输入

4 21 9 28 9 28 3 17 4

输出

21

说明/提示

样例解释：

众数出现次数最多是 3 次，有如下两种方法：

• 1 号同学直接出红卡，2 号同学出红黑异或，3 号同学随便出，4 号同学出红黑异或。这样 1,2,4 号同学都可以打出 21。
• 1 号同学出红黑异或，2 号同学直接出红卡，3 号同学直接出红卡，4 号同学随便出。这样 1,2,3 号同学都可以打出 28。

所以 21 和 28 都是出现次数最多的众数，因为最多可以出现 3 次，不存在出现 4 次的方案。但是由于要求如果有多解输出小的，请输出 21。

以下是我的题解，利用了哈希表键值不能重复的特性统计了每个数字出现的次数，从而达到解题的目的。

#include <bits/stdc++.h> #include <unordered_map> using namespace std; int main() { int n; cin >> n; unordered_map<long long, int> count; for (int i = 0; i < n; i++) { long long a, b; cin >> a >> b; long long result = a ^ b;//计算两个数字异或的结果 if (a == result) { count[a]++; } else { count[a]++; count[result]++; } } int max = 0; long long min = 1000000001; for (auto& i : count) {//由于哈希表中的数据没有顺序的概念，所以使用auto来遍历整个哈希表 long long num = i.first;//对应前面long long类型数据 int cnt = i.second;//对应数据出现的次数 if (cnt > max) { max = cnt; min = num; } else if (cnt == max && num < min) { min = num;//当出现次数相同时，选择较小的那个数字 } } cout << min << endl; return 0; }