优秀学员统计 - 华为OD统一考试(E卷)

2024华为OD机试（E卷+D卷+C卷）最新题库【超值优惠】Java/Python/C++合集

题目描述

公司某部门软件教导团正在组织新员工每日打卡学习活动，他们开展这项学习活动已经一个月了，所以想统计下这个月优秀的打卡员工。每个员工会对应一个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

题解

本题的目的是从一个包含30天打卡记录的列表中，统计出打卡次数最多的前5名员工。

如果打卡次数相同，则按最早参与打卡的时间排序；如果时间也相同，则按员工ID的大小排序。

这题属于排序和统计类问题。

解题思路

1. 数据结构设计：需要使用一个数组记录每个员工的打卡次数，以及一个数组记录每个员工的最早打卡时间。

2. 输入处理：首先输入员工数量，然后输入30天的打卡信息，逐天记录每个员工的打卡次数及最早打卡时间。

3. 排序规则

   ：

   • 主要依据打卡次数进行降序排列。
   • 如果打卡次数相同，依据最早打卡时间升序排列。
   • 如果打卡次数和最早打卡时间相同，则依据员工ID升序排列。

4. 输出前5名员工：根据排序结果输出前5名员工的ID。

算法复杂度

• 时间复杂度：输入处理部分的时间复杂度是O(30×N)，其中N为员工数量，30是天数。排序部分的时间复杂度是O(N log N)。
• 空间复杂度：主要是存储员工打卡次数、最早打卡时间及排序用的辅助数据，空间复杂度为O(N)。

Java

import java.util.*;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // freq[id] 表示 id 学员的总打卡次数
        int[] freq = new int[n];
        // earliestTime[id] 表示 id 学员的最早打卡时间
        int[] earliestTime = new int[n];
        Arrays.fill(earliestTime, Integer