描述

输入描述:

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

输出描述:

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

示例

输入:
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为输入的学生成绩数