华为OD机试 - 找出作弊的人（Java 2024 E卷 100分）

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

公司组织了一次考试, 现在考试结果出来了，想看一下有没有人存在作弊行为, 但是员工太多了, 需要先对员工进行一次过滤，再进一步确定是否存在作弊行为。

过滤的规则为：找到分差最小的员工ID对(p1, p2)列表，要求p1 < p2。

1. 员工个数取值范围：0 < n < 100000
2. 员工ID为整数，取值范围：0 <= n <= 100000
3. 考试成绩为整数，取值范围：0 <= score <= 300

二、输入描述

员工的ID及考试分数

三、输出描述

分差最小的员工ID对(p1, p2)列表，要求p1 < p2。每一行代表一个集合，每个集合内的员工ID按顺序排列，多行结果也以员工ID对中p1值大小升序排列（如果p1相同则p2升序）。

四、测试用例

测试用例1：

1、输入

5
1 90
2 91
3 95
4 96
5 100

2、输出

1 2
3 4

3、说明

按照分数对员工进行排序，若分数相同，则按照员工ID排序。经过排序，员工的顺序如下：

[1, 90], [2, 91], [3, 95], [4, 96], [5, 100]

我们计算相邻员工的分数差，找到分差最小的情况：

1. 员工1 和 员工2 的分数差：91 - 90 = 1
2. 员工2 和 员工3 的分数差：95 - 91 = 4
3. 员工3 和 员工4 的分数差：96 - 95 = 1
4. 员工4 和 员工5 的分数差：100 - 96 = 4

最小分差为 1。

找到分差等于最小分差的员工对：

分差为 1 的员工对有两个：

• 员工1 和 员工2（分数分别为 90 和 91，ID分别为 1 和 2）
• 员工3 和 员工4（分数分别为 95 和 96，ID分别为 3 和 4）

因为已经按分数和ID排序，我们可以直接将员工对按照 p1 < p2 的顺序输出：

1 2
3 4

测试用例2：

1、输入

5
1 90
2 91
3 92
4 85
5 86

2、输出

1 2
2 3
4 5

3、说明

按照分数对员工进行排序，若分数相同，则按照员工ID排序。经过排序，员工的顺序如下：

[4, 85], [5, 86], [1, 90], [2, 91], [3, 92]

计算相邻员工的分数差，找到分差最小的情况：

• 员工4 和 员工5 的分数差：86 - 85 = 1
• 员工5 和 员工1 的分数差：90 - 86 = 4
• 员工1 和 员工2 的分数差：91 - 90 = 1
• 员工2 和 员工3 的分数差：92 - 91 = 1

最小分差为 1。

找到分差等于最小分差的员工对：

• 员工4 和 员工5（分数分别为 85 和 86，ID分别为 4 和 5）
• 员工1 和 员工2（分数分别为 90 和 91，ID分别为 1 和 2）
• 员工2 和 员工3（分数分别为 91 和 92，ID分别为 2 和 3）

由于我们要按ID对升序排列输出，因此这些对已经按ID顺序排列，无需进一步排序，最终输出为：

1 2
2 3
4 5

五、解题思路

1、具体步骤：

使用一个二维数组 employees 来存储员工的ID和考试分数。然后按照分数进行排序，这样我们可以通过遍历相邻的员工来找到分数最小的差值对。

对员工按分数进行排序后，分差最小的一定在相邻的两个人之间。因此，我们只需要遍历排序后的员工列表，计算相邻员工分数的差值，找到最小差值并记录所有满足条件的员工ID对。

要求输出时 p1 < p2，即员工ID小的在前。如果两个员工ID相等，则按照ID大小输出。这通过在排序时按分数排列，之后处理ID对时可以自动确保输出顺序。

2、时间复杂度

排序：Arrays.sort 的时间复杂度是 O(n log n)，其中 n 是员工数量。在最坏的情况下，n 可能达到 100,000。

遍历和计算分差：我们需要两次遍历员工数组来计算最小分差和找出满足条件的ID对，每次遍历的时间复杂度都是 O(n)。

结果排序：我们对找到的结果进行一次排序，时间复杂度是 O(m log m)，其中 m 是最小分差的员工对数量。

因此，总的时间复杂度为 O(n log n)，排序操作在这里占主导地位。

3、空间复杂度

二维数组：存储员工的ID和分数的数组的大小是 O(n)，其中 n 是员工的数量。

列表 (List<int[]>)：用于存储最小分差的员工ID对，其空间复杂度是 O(m)，其中 m 是最小分差的员工对数量。

辅助空间：排序算法 Arrays.sort 使用 O(n) 的辅助空间来处理。

因此，空间复杂度为 O(n)，因为我们只需存储员工ID和分数，外加一个列表存储结果。

六、Java算法源码

public class OdTest01 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取员工个数int n = scanner.nextInt();int[][] employees = new int[n][2]; // 二维数组存储员工ID和分数// 读取员工ID和分数for (int i = 0; i < n; i++) {employees[i][0] = scanner.nextInt();  // 员工IDemployees[i][1] = scanner.nextInt();  // 员工分数}// 调用方法处理并输出结果List<int[]> result = findCheatingPairs(employees);// 按照格式输出for (int[] pair : result) {System.out.println(pair[0] + " " + pair[1]);}scanner.close();}// 查找分差最小的员工对public static List<int[]> findCheatingPairs(int[][] employees) {List<int[]> result = new ArrayList<>();// 按分数排序，如果分数相同，则按员工ID排序Arrays.sort(employees, (a, b) -> {if (a[1] != b[1]) return a[1] - b[1];  // 按分数排序return a[0] - b[0];  // 如果分数相同，则按ID排序});// 找到最小分差int minDiff = Integer.MAX_VALUE;for (int i = 1; i < employees.length; i++) {int diff = employees[i][1] - employees[i - 1][1];minDiff = Math.min(minDiff, diff);}// 找到所有分差等于最小分差的对for (int i = 1; i < employees.length; i++) {int diff = employees[i][1] - employees[i - 1][1];if (diff == minDiff) {int p1 = Math.min(employees[i][0], employees[i - 1][0]);int p2 = Math.max(employees[i][0], employees[i - 1][0]);result.add(new int[] {p1, p2});}}// 按p1升序排序，如果p1相同则按p2排序result.sort((a, b) -> {if (a[0] != b[0]) return a[0] - b[0];return a[1] - b[1];});return result;}
}

七、效果展示

1、输入

5
1 60
2 65
3 70
4 75
5 85

2、输出

1 2
2 3
3 4

3、说明

🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 E卷 200分）

🏆本文收录于，华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。