华为OD机试 - 找出作弊的人（Python/JS/C/C++ 2024 E卷 100分）

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

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/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和分数，外加一个列表存储结果。

六、Python算法源码

def find_cheating_pairs(employees):
    # 按分数排序，如果分数相同，则按员工ID排序
    employees.sort(key=lambda x: (x[1], x[0]))

    # 找到最小分差
    min_diff = float('inf')
    for i in range(1, len(employees)):
        diff = employees[i][1] - employees[i - 1][1]
        min_diff = min(min_diff, diff)

    result = []

    # 找到所有分差等于最小分差的对
    for i in range(1, len(employees)):
        diff = employees[i][1] - employees[i - 1][1]
        if diff == min_diff:
            p1 = min(employees[i][0], employees[i - 1][0])
            p2 = max(employees[i][0], employees[i - 1][0])
            result.append([p1, p2])

    # 按p1升序排序，如果p1相同则按p2排序
    result.sort(key=lambda x: (x[0], x[1]))

    return result

if __name__ == "__main__":
    # 读取员工个数
    n = int(input())
    employees = []

    # 读取员工ID和分数
    for _ in range(n):
        emp_id, score = map(int, input().split())
        employees.append([emp_id, score])

    # 调用方法处理并输出结果
    result = find_cheating_pairs(employees)

    # 按照格式输出
    for pair in result:
        print(f"{pair[0]} {pair[1]}")

七、JavaScript算法源码

function findCheatingPairs(employees) {
    // 按分数排序，如果分数相同，则按员工ID排序
    employees.sort((a, b) => {
        if (a[1] !== b[1]) return a[1] - b[1];  // 按分数排序
        return a[0] - b[0];  // 如果分数相同，则按ID排序
    });

    // 找到最小分差
    let minDiff = Infinity;
    for (let i = 1; i < employees.length; i++) {
        let diff = employees[i][1] - employees[i - 1][1];
        minDiff = Math.min(minDiff, diff);
    }

    const result = [];

    // 找到所有分差等于最小分差的对
    for (let i = 1; i < employees.length; i++) {
        let diff = employees[i][1] - employees[i - 1][1];
        if (diff === minDiff) {
            let p1 = Math.min(employees[i][0], employees[i - 1][0]);
            let p2 = Math.max(employees[i][0], employees[i - 1][0]);
            result.push([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;
}

// 读取输入并处理结果
function main() {
    const n = parseInt(prompt("请输入员工个数:"));
    const employees = [];

    // 读取员工ID和分数
    for (let i = 0; i < n; i++) {
        const input = prompt("请输入员工ID和分数:").split(' ').map(Number);
        employees.push([input[0], input[1]]);
    }

    // 调用方法处理并输出结果
    const result = findCheatingPairs(employees);

    // 按照格式输出
    result.forEach(pair => {
        console.log(pair[0] + " " + pair[1]);
    });
}

// 调用主函数
main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int id;
    int score;
} Employee;

// 比较函数用于排序员工
int compare(const void *a, const void *b) {
    Employee *emp1 = (Employee *)a;
    Employee *emp2 = (Employee *)b;
    
    if (emp1->score != emp2->score) {
        return emp1->score - emp2->score;  // 按分数排序
    } else {
        return emp1->id - emp2->id;  // 如果分数相同，按ID排序
    }
}

// 查找分差最小的员工对
void findCheatingPairs(Employee *employees, int n) {
    // 首先对员工按分数和ID排序
    qsort(employees, n, sizeof(Employee), compare);

    // 找到最小分差
    int minDiff = 300;  // 最大分数差为300
    for (int i = 1; i < n; i++) {
        int diff = employees[i].score - employees[i - 1].score;
        if (diff < minDiff) {
            minDiff = diff;
        }
    }

    // 找到所有分差等于最小分差的员工对
    for (int i = 1; i < n; i++) {
        int diff = employees[i].score - employees[i - 1].score;
        if (diff == minDiff) {
            int p1 = employees[i - 1].id;
            int p2 = employees[i].id;
            if (p1 < p2) {
                printf("%d %d\n", p1, p2);
            } else {
                printf("%d %d\n", p2, p1);
            }
        }
    }
}

int main() {
    int n;

    // 读取员工个数
    printf("请输入员工个数: ");
    scanf("%d", &n);

    Employee employees[n];

    // 读取员工ID和分数
    for (int i = 0; i < n; i++) {
        printf("请输入员工ID和分数: ");
        scanf("%d %d", &employees[i].id, &employees[i].score);
    }

    // 查找分差最小的员工对并输出
    findCheatingPairs(employees, n);

    return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义员工结构体
struct Employee {
    int id;
    int score;
};

// 比较函数，用于排序员工
bool compare(const Employee &a, const Employee &b) {
    if (a.score != b.score) {
        return a.score < b.score;  // 按分数排序
    } else {
        return a.id < b.id;  // 如果分数相同，按ID排序
    }
}

// 查找分差最小的员工对
vector<pair<int, int>> findCheatingPairs(vector<Employee> &employees) {
    vector<pair<int, int>> result;

    // 首先对员工按分数和ID排序
    sort(employees.begin(), employees.end(), compare);

    // 找到最小分差
    int minDiff = INT_MAX;
    for (int i = 1; i < employees.size(); i++) {
        int diff = employees[i].score - employees[i - 1].score;
        minDiff = min(minDiff, diff);
    }

    // 找到所有分差等于最小分差的员工对
    for (int i = 1; i < employees.size(); i++) {
        int diff = employees[i].score - employees[i - 1].score;
        if (diff == minDiff) {
            int p1 = min(employees[i].id, employees[i - 1].id);
            int p2 = max(employees[i].id, employees[i - 1].id);
            result.push_back(make_pair(p1, p2));
        }
    }

    // 按p1升序排序，如果p1相同则按p2排序
    sort(result.begin(), result.end());

    return result;
}

int main() {
    int n;

    // 读取员工个数
    cout << "请输入员工个数: ";
    cin >> n;

    vector<Employee> employees(n);

    // 读取员工ID和分数
    for (int i = 0; i < n; i++) {
        cout << "请输入员工ID和分数: ";
        cin >> employees[i].id >> employees[i].score;
    }

    // 查找分差最小的员工对并输出
    vector<pair<int, int>> result = findCheatingPairs(employees);

    // 输出结果
    for (const auto &pair : result) {
        cout << pair.first << " " << pair.second << endl;
    }

    return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

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