刷题笔记合集🔗

优秀学员统计

问题描述

A企业的软件教导团正在组织新员工每日打卡学习活动，他们开展这项学习活动已经一个月了，所以想统计下这个月优秀的打卡员工。每个员工会对应一个id，每天的打卡记录记录当天打卡员工的id集合，一共30天。

请你实现代码帮助统计出打卡次数top5的员工。如果打卡次数相同，将较早参与打卡的员工排在前面，如果开始参与打卡的时间还是一样，将id较小的员工排在前面。

注：不考虑并列的情况，按规则返回前5名员工的id即可，如果当月打卡的员工少于5个，按规则排序返回所有有打卡记录的员工id。

输入格式

第一行输入为新员工数量 ，表示新员工编号id为 到 ， 的范围为 。

第二行输入为 个整数，表示每天打卡的员工数量，每天至少有 名员工打卡。

之后 行为每天打卡的员工id集合，id不会重复。

输出格式

按顺序输出打卡top5员工的id，用空格隔开。

样例输入

11
4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2
0 1 7 10
0 1 6 10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
6 10
7 10

7
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5

样例输出

10 0 1 7 6

0 1 2 3 4

数据范围

• 
• 每天至少有1名员工打卡

题解

这是一道关于排序和统计的问题。我们需要统计每个员工的打卡次数以及首次打卡的日期，然后按照要求的规则进行排序。

首先，我们需要创建一个数据结构来保存每个员工的信息。对于每个员工，我们需要记录：

1. 员工ID
2. 打卡次数
3. 首次打卡的日期

然后，我们遍历所有的打卡记录。对于每天的打卡记录：

• 如果员工已经在我们的数据结构中，就增加其打卡次数
• 如果员工还没有记录，则添加这个员工，并记录当前的日期为首次打卡日期

最后，我们按照以下规则对员工进行排序：

1. 打卡次数从高到低
2. 如果打卡次数相同，则按照首次打卡日期从早到晚
3. 如果首次打卡日期也相同，则按照员工ID从小到大

排序完成后，我们取前5名员工（如果总员工数少于5，则取所有员工）的ID作为结果输出。

时间复杂度分析：遍历所有打卡记录的时间复杂度为O(30N)，排序的时间复杂度为O(NlogN)，所以总的时间复杂度为O(N*logN)，其中N是员工数量。对于给定的约束条件（N最大为100），这个时间复杂度是完全可以接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
n = int(input())
day_counts = list(map(int, input().split()))
day_ids = []
for i in range(30):
    day_ids.append(list(map(int, input().split())))

# 统计每个员工的打卡次数和首次打卡日期
def find_top_employees(day_records):
    emp_data = {}  # 使用字典存储员工数据
    
    # 遍历每天的打卡记录
    for day, ids in enumerate(day_records):
        for emp_id in ids:
            if emp_id in emp_data:
                # 已有记录，增加打卡次数
                emp_data[emp_id]["cnt"] += 1
            else:
                # 新员工，记录首次打卡日期
                emp_data[emp_id] = {
                    "cnt": 1,
                    "first_day": day
                }
    
    # 将字典转换为列表以便排序
    result = []
    for emp_id, data in emp_data.items():
        result.append((emp_id, data["cnt"], data["first_day"]))
    
    # 按规则排序：先按打卡次数降序，次数相同则按首次打卡日期升序，日期相同则按ID升序
    result.sort(key=lambda x: (-x[1], x[2], x[0]))
    
    # 返回前5名员工ID（若不足5名则返回全部）
    return " ".join(map(str, [x[0] for x in result[:5]]))

# 输出结果
print(find_top_employees(day_ids))

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 读取每天打卡人数
    vector<int> day_cnt(30);
    for (int i = 0; i < 30; i++) {
        cin >> day_cnt[i];
    }
    
    // 读取每天打卡的员工ID
    vector<