描述

输入描述：

输入多行，先输入要排序的人的个数，然后分别输入他们的名字和成绩，以一个空格隔开

输出描述：

按照指定方式输出名字和成绩，名字和成绩之间以一个空格隔开

示例

输入：
3
0
fang 90
yang 50
ning 70
输出：
fang 90
ning 70
yang 50

知识点：模拟，排序

难度：⭐⭐⭐

题解

方法一：自定义排序

图解：

解题思路：

算法流程：

• 通过一个二维数组，每一行包括姓名编号，成绩，将输入的姓名用编号代替，第二列保存成绩
• 自定义排序
  • 倒序，按第二列的成绩降序排列,如果相等的话，返回0，顺序不变，因为默认编号是升序的，符合题意
  • 升序则 按成绩升序排序
• 最后根据已经排序后的数组，顺序输出结果

Java 版本代码如下：

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        HashMap<Integer,String> map = new HashMap<>();
        while(sc.hasNextLine()){
            // 学生成绩数
            int n = Integer.parseInt(sc.nextLine());
            //1是升序，0是降序
            int flag = Integer.parseInt(sc.nextLine());
            // 每一行包括姓名编号，成绩
            int[][] score = new int[n][2];
            for(int i=0;i<n;i++){
                String[] nameAndScore = sc.nextLine().split(" ");
                // 学生用编号代替
                score[i][0] = i;
                score[i][1] = Integer.parseInt(nameAndScore[1]);
                map.put(i,nameAndScore[0]);
            }
            // 自定义排序
            Arrays.sort(score,(o1,o2) ->{
                // 倒序，按第二列的成绩降序排列,如果相等的话，返回0，顺序不变，因为默认编号是升序的，符合题意
                if(flag==0){
                    return o2[1] - o1[1];
                }else{
                    // 按成绩升序排序
                    return o1[1] - o2[1];
                }
            });
            // 根据已经排序后的数组，顺序输出结果
            for(int i=0;i<n;i++){
                System.out.println(map.get(score[i][0]) + " " + score[i][1]);
            }
        }
    }
}

复杂度分析：

时间复杂度：$O(nlogn)O(nlogn)$， 保存二维数组需要遍历每个学生成绩, 且使用了排序，n为输入的学生成绩数

空间复杂度：$O(n)O(n)$， 二维数组固定两列，因此总的空间为O(n)，n为输入的学生成绩数