题目描述

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

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

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

输入描述

• 第一行输入为新员工数量 N，表示新员工编号 id 为 0 到 N-1。
• 第二行输入为30个整数，表示每天打卡的员工数量，每天至少有1名员工打卡。
• 之后30行为每天打卡的员工 id 集合，id 不会重复。

输出描述

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

题解思路

我们要通过打卡记录统计每个员工的打卡次数，并按以下规则进行排序：

1. 打卡次数最多的排前面。
2. 打卡次数相同的，先打卡的员工排前面。
3. 打卡次数和打卡顺序都相同的，id 小的员工排前面。

具体步骤：

1. 记录打卡信息：

   • 使用一个 dict/map 来记录每个员工的打卡次数。
   • 使用一个 dict/map 来记录每个员工首次打卡的天数。

2. 排序：

   • 根据员工的打卡次数、首次打卡天数以及 id 来排序。
   • 结果只取前5个员工。

复杂度分析

• 时间复杂度：O(30 * N)，最多需要遍历30天的打卡记录，每天最多有 N 名员工。
• 空间复杂度：O(N)，需要存储每个员工的打卡次数和首次打卡的日期。

代码实现

C++

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

int main() {
    int n;
    cin >> n;

    vector<int> count(30);
    for (int day = 0; day < 30; day++) {
        cin >> count[day];  // 读取每天打卡的员工数量
    }

    map<int, int> freq;     // 记录每个员工的打卡次数
    map<int, int> firstDay; // 记录每个员工首次打卡的天数

    // 读取每一天的打卡记录
    for (int day = 0; day < 30; day++) {
        for (int i = 0; i < count[day]; i++) {
            int id;
            cin >> id;
            freq[id]++;  // 统计打卡次数
            if (firstDay.find(id) == firstDay.end()) {
                firstDay[id] = day;  // 记录首次打卡的天数
            }
        }
    }

    // 将所有员工的ID收集到一个数组中
    vector<int> ids;
    for (const auto [id, y] : freq) {
        ids.push_back(id);
    }

    // 按照打卡次数、首次打卡天数和ID排序
    sort(ids.begin(), ids.end(), [&](int x, int y) {
        if (freq[x] != freq[y]) {
            return freq[x] > freq[y];  // 按打卡次数降序
        }
        if (firstDay[x] != firstDay[y]) {
            return firstDay[x] < firstDay[y];  // 按首次打卡天数升序
        }
        return x < y;  // 按ID升序
    });

    // 输出前5个员工的ID
    for (int i = 0; i < min((int) ids.size(), 5); i++) {
        cout << ids[i] << " ";
    }

    return 0;
}

Python

def main():
    # 读取新员工数量
    n = int(input())

    # 读取每天打卡员工数量
    count = list(map(int, input().split()))

    # 记录员工的打卡次数和首次打卡的天数
    freq = {}
    firstDay = {}

    # 读取每一天的打卡记录
    for day in range(30):
        ids = list(map(int, input().split()))
        for id in ids:
            if id not in freq:
                freq[id] = 0
            freq[id] += 1
            if id not in firstDay:
                firstDay[id] = day

    # 将员工ID按规则排序
    sorted_ids = sorted(freq.keys(), key=lambda x: (-freq[x], firstDay[x], x))

    # 输出前5个员工的ID
    print(" ".join(map(str, sorted_ids[:5])))

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取新员工数量
        int n = sc.nextInt();
        sc.nextLine();  // 读取换行符

        // 读取每天打卡员工数量
        int[] count = new int[30];
        String[] countInput = sc.nextLine().split(" ");
        for (int i = 0; i < 30; i++) {
            count[i] = Integer.parseInt(countInput[i]);
        }

        // 记录员工的打卡次数和首次打卡的天数
        Map<Integer, Integer> freq = new HashMap<>();
        Map<Integer, Integer> firstDay = new HashMap<>();

        // 读取每一天的打卡记录
        for (int day = 0; day < 30; day++) {
            String[] ids = sc.nextLine().split(" ");
            for (String idStr : ids) {
                int id = Integer.parseInt(idStr);
                freq.put(id, freq.getOrDefault(id, 0) + 1);
                if (!firstDay.containsKey(id)) {
                    firstDay.put(id, day);
                }
            }
        }

        // 按照打卡次数、首次打卡天数和ID排序
        List<Integer> sortedIds = new ArrayList<>(freq.keySet());
        sortedIds.sort((x, y) -> {
            if (freq.get(x) != freq.get(y)) {
                return freq.get(y) - freq.get(x);  // 按打卡次数降序
            }
            if (firstDay.get(x) != firstDay.get(y)) {
                return firstDay.get(x) - firstDay.get(y);  // 按首次打卡天数升序
            }
            return x - y;  // 按ID升序
        });

        // 输出前5个员工的ID
        for (int i = 0; i < Math.min(sortedIds.size(), 5); i++) {
            System.out.print(sortedIds.get(i) + " ");
        }
    }
}

题目描述

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

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

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

输入描述

第一行输入为新员工数量 $N$ ，表示新员工编号 $id$ 为 $0$ 到 $N-1$，$N$ 的范围为 $[1,100]$

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

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

输出描述

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

样例1

输入

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

输出

10 0 1 7 6

说明

员工编号范围为 $0$ ~ $10$ ，$id$ 为 $10$ 的员工连续打卡 $30$ 天，排第一，$id$ 为 $0$,$1$,$6$,$7$ 的员工打卡都是两天，$id$ 为 $0$,$1$,$7$ 的员工在第一天就打卡，比 $id$ 为 $6$ 的员工早，排在前面，$0$,$1$,$7$ 按 $id 升序排列，所以输出$[10,0,1,7,6]$

样例2

输入

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

输出

0 1 2 3 4

说明

员工编号范围为 $0$-$6$ ， $id$ 为 $0$，$1$，$2$，$3$，$4$，$5$ 的员工打卡次数相同，最早开始打卡的时间也一样，所以按 $id$ 升序返回前 $5$ 个 $id$

样例3

输入

2
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 1 1 2 2
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
1
1
0 1
0 1

输出

1 0

说明

只有两名员工参与打卡，按规则排序输出两名员工的 $id$