寻找身高最相近的小朋友 - 华为OD统一考试(D卷)

OD统一考试（D卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

小明今年升学到小学一年级，来到新班级后发现其他小朋友们身高参差不齐，然后就想基于各小朋友和自己的身高差对他们进行排序，请帮他实现排序。

输入描述

第一行为正整数H和N，0<H<200，为小明的身高，0<N<50，为新班级其他小朋友个数。

第二行为N个正整数H1-HN，分别是其他小朋友的身高，取值范围0<Hi<200 (1<= i <=N)，且N个正整数各不相同。

输出描述

输出排序结果，各正整数以空格分割。和小明身高差绝对值最小的小朋友排在前面，和小明身高差绝对值最大的小朋友排在最后，如果两个小朋友和小明身高差一样，则个子较小的小朋友排在前面。

示例1

输入：
100 10
95 96 97 98 99 101 102 103 104 105

输出：
99 101 98 102 97 103 96 104 95 105

说明：
小明身高100，班级学生10个，身高分别为95 96 97 98 99 101 102 103 104 105，按身高差排序后结果为: 99 101 98 102 97 103 96 104 95 105。

题解

这道题属于排序算法的应用。解题思路是计算每个同学的身高与小明身高的差值，然后按照这个差值进行排序，如果差值相同，则按照身高进行排序。接着输出排序后的结果即可。

时间复杂度分析

Java 和 C++ 版本的时间复杂度为 O(NlogN)，其中 N 为小朋友的数量，主要由排序算法决定。

Python 版本同样是 O(NlogN)，排序的时间复杂度为 O(NlogN)，遍历输出的时间复杂度为 O(N)。

空间复杂度分析

Java 和 Python 版本的空间复杂度为 O(N)，主要用于存储同学的信息。

C++ 版本的空间复杂度也是 O(N)，存储同学信息的 vector 占用了空间。

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 小明身高， 班级其他小朋友个数
        int h = in.nextInt(), n = in.nextInt();

        // 存放小朋友信息: new int[]{和小明身高差绝对值, 小朋友身高}
        List<int[]> hs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int height = in.nextInt();
            hs.add(new int[]{Math.abs(h - height), height});
        }

        // 根据 “和小明身高差绝对值” 和 “小朋友身高” 排序
        hs.sort((a, b) -> (a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]));

        // 构造结果并打印
        StringBuffer rs = new StringBuffer();
        for (int i = 0; i < n; i++) {
            rs.append(hs.get(i)[1]).append(" ");
        }
        System.out.println(rs.toString().trim());
    }
}

Python

def main():
    # 输入：小明的身高，其他同学的数量
    h, n = map(int, input().split())

    # 存储同学信息的列表：[与小明身高的绝对差值, 同学的身高]
    classmates = []
    for height in map(int, input().split()):
        classmates.append((abs(h - height), height))

    # 根据绝对差值和身高排序
    classmates.sort(key=lambda x: (x[0], x[1]))

    # 结果打印
    print(*[h[1] for h in classmates])


if __name__ == "__main__":
    main()

C++

#include <bits/stdc++.h>

using namespace std;

// 根据绝对差值和身高比较两个pair的函数
bool compare(pair<int, int> a, pair<int, int> b)
{
    if (a.first != b.first) {
        return a.first < b.first;
    } else {
        return a.second < b.second;
    }
}

int main()
{
    // 输入：小明的身高，其他同学的数量
    int h, n;
    cin >> h >> n;

    // 存储同学信息的向量：{与小明身高的绝对差值, 同学的身高}
    vector<pair<int, int>> classmates;
    for (int i = 0; i < n; i++) {
        int height;
        cin >> height;
        classmates.push_back({abs(h - height), height});
    }

    // 根据绝对差值和身高排序
    sort(classmates.begin(), classmates.end(), compare);

    // 结果打印
    for (int i = 0; i < n; i++) {
        if (i + 1 == n) {
            cout << classmates[i].second << endl;
        } else {
            cout << classmates[i].second << " ";
        }
    }

    return 0;
}