蓝桥杯真题——班级活动
目录
题目链接：1.班级活动 - 蓝桥云课
题目描述
输入格式
输出格式
样例输入
样例输出
样例说明
评测用例规模与约定
解法一：Map集合处理
举个例子
Java写法：
C++写法：
运行时间
时间复杂度和空间复杂度
时间复杂度
空间复杂度
总结
题目链接：1.班级活动 - 蓝桥云课
注：下述题目描述和示例均来自蓝桥云客
题目描述
小明的老师准备组织一次班级活动。班上一共有 n 名 (n 为偶数) 同学，老师想把所有的同学进行分组，每两名同学一组。为了公平，老师给每名同学随机分配了一个 n 以内的正整数作为 id，第 i 名同学的 id 为 ai。
老师希望通过更改若干名同学的 id 使得对于任意一名同学 i，有且仅有另一名同学 j 的 idid 与其相同 (ai=aj)。请问老师最少需要更改多少名同学的 id？
输入格式
输入共 22 行。
第一行为一个正整数 nn。
第二行为 nn 个由空格隔开的整数 a1,a2,...,ana1,a2,...,an。
输出格式
输出共 11 行，一个整数。
样例输入
4
1 2 2 3
样例输出
1
样例说明
仅需要把 a1a1 改为 33 或者把 a3a3 改为 11 即可。
评测用例规模与约定
对于 20% 的数据，保证 n≤10^3。
对于 100% 的数据，保证 n≤10^5。
解法一：Map集合处理
-
读取输入并统计数字出现次数
使用unordered_map来记录每个数字的出现次数。我们遍历输入的n个数字，对于每个数字num，在哈希表map中更新其出现次数。- 如果数字
num已存在于map中，则增加其对应的计数值。 - 如果
num不存在，则将其加入map，并将计数值初始化为1。
- 如果数字
-
分类统计：确定多次出现和单次出现的情况
遍历map中的每个键值对，统计出现次数的分布：-
超过两次出现的情况：如果一个数字的出现次数大于2次（即
map[num] > 2），则记下“超出2次的总数”。我们将这些多余的出现次数累加到moreNum中，因为这些多余的出现次数需要修改为其他数字以满足要求。 -
等于一次出现的情况：如果一个数字的出现次数等于1次（即
map[num] == 1），则计数到oneNum中。这些一次出现的数字可以用于和“多次出现的数字”配对，使得不超过两次的条件得到满足。
-
-
计算最小修改次数
根据moreNum和oneNum的值，决定最小修改次数：-
情况1：如果多余次数
moreNum已经大于或等于oneNum，则这些多余次数的一部分可以和oneNum进行配对，使得这些出现一次的数字不需要修改，剩余的多余次数将直接计入修改次数。 -
情况2：如果多余次数
moreNum小于oneNum，那么可以让moreNum的所有多余次数和oneNum的一部分配对。之后，剩余的oneNum还需要一半的数量修改为其他数字才能满足条件。
-
举个例子
假设我们有以下输入：3, 3, 3, 5, 5, 6。
-
第一步：统计出现次数，得到
map = {3: 3, 5: 2, 6: 1}。 -
第二步：遍历
map，得到moreNum = 1（3出现了3次，超过了2次），oneNum = 1（6出现了1次）。 -
第三步：根据
moreNum和oneNum的关系判断需要的修改次数。在这里，
moreNum和oneNum相等，因此只需要moreNum = 1次修改，使得3的出现次数减少到2即可满足条件。
Java写法：
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//在此输入您的代码...int n = sc.nextInt();Map<Integer,Integer> map = new HashMap<>();for(int i = 0;i < n;i++){// 将其对应出现的次数+1int num = sc.nextInt();map.put(num, map.getOrDefault(num, 0) + 1);}// 记录超过2的数量int moreNum = 0;// 记录超过1的数量int oneNum = 0;for(Integer value: map.values()){if(value > 2){// 超过了2两个moreNum += value - 2;}else if(value == 2){continue;}else{// 那就是一个oneNum++;}}// 如果比单独的多，那么就是moreNum的值，一部分用于和oneNum配对，剩下的两个都需要修改为其他的目标if(moreNum >= oneNum){System.out.print(moreNum);}else{//这种情况就是moreNum全和oneNum配对，然后剩余的oneNum的一半修改即可System.out.print(moreNum + (oneNum - moreNum)/2);}sc.close();}
}
C++写法：
#include <iostream>
#include <unordered_map>
using namespace std;int main() {int n;cin >> n;unordered_map<int, int> map;for(int i = 0; i < n; i++) {int num;cin >> num;map[num] += 1;}int moreNum = 0; // 记录超过2的数量int oneNum = 0; // 记录仅出现1次的数量for(const auto& pair : map) {int value = pair.second;if(value > 2) {moreNum += value - 2; // 超过2次的部分计入moreNum} else if(value == 1) {oneNum++; // 仅出现1次的部分计入oneNum}}if(moreNum >= oneNum) {cout << moreNum;} else {cout << moreNum + (oneNum - moreNum) / 2;}return 0;
}
运行时间
时间复杂度和空间复杂度
时间复杂度
-
输入读取和统计出现次数：第一部分是用一个循环读取输入的
n个整数，并统计每个数字的出现次数。这部分使用了一个哈希表unordered_map，并在每次读取一个数字时执行map[num] += 1操作。由于哈希表的插入和查找操作的平均时间复杂度是 O(1)，因此这部分的时间复杂度是 O(n)。 -
统计出现次数大于2和等于1的数字：第二部分对
unordered_map的每个值进行一次遍历，统计出现次数大于2的数字和等于1的数字。因为哈希表中最多有n个不同的数字，这部分的时间复杂度也是 O(n)。
综上所述，总的时间复杂度为：
O(n)+O(n)=O(n)
空间复杂度
-
哈希表
unordered_map：用于存储每个数字的出现次数。在最坏情况下，如果所有的n个数字都不相同，哈希表中将包含n个键值对，因此其空间复杂度是 O(n)。 -
常数空间：程序中还使用了一些整数变量（如
moreNum和oneNum）来记录特定统计信息，这些变量占用的空间是常数级别 O(1)。
因此，空间复杂度为：O(n)
总结
总结
本文讨论了一个关于班级分组的问题，其中老师需要将偶数名同学进行两两配对，使得每两名同学的ID相同。
题目描述
- 老师有n名（n为偶数）同学，并给每名同学分配了一个n以内的正整数ID。
- 老师希望通过更改若干名同学的ID，使得对于任意一名同学i，有且仅有另一名同学j的ID与其相同。
- 询问老师最少需要更改多少名同学的ID。
解法一：Map集合处理
- 步骤：
- 使用Map集合（如HashMap或UnorderedMap）来记录每个ID出现的次数。
- 遍历所有同学的ID，更新Map中对应ID的计数。
- 遍历Map，统计出现次数超过2次的ID的额外数量（moreNum，即超过2次的部分），以及只出现1次的ID数量（oneNum）。
- 根据moreNum和oneNum的关系，计算最少需要更改的ID数量：
- 如果moreNum >= oneNum，则直接输出moreNum，因为moreNum部分可以通过两两配对消耗掉，剩下的也可以用来配对oneNum部分，但不需要额外修改。
- 如果moreNum < oneNum，则输出moreNum + (oneNum - moreNum) / 2，因为moreNum部分可以全部配对，剩下的oneNum部分需要两两配对，因此只需要修改剩余oneNum的一半数量。
- 时间复杂度和空间复杂度：
- 时间复杂度：O(n)，其中n是同学的数量，因为我们需要遍历所有同学的ID两次（一次用于填充Map，一次用于统计moreNum和oneNum）。
- 空间复杂度：O(n)，因为Map集合在最坏情况下需要存储n个不同的ID及其计数。