排序算法题

发表于 2024-02-28 分类于技术阅读次数：

前言：近期刷过的基础排序算法题的记录与总结。

常用方法：

Arrays.sort()快排与其可以自行制定规则的匿名内部类写法(?)

大致样式：

Arrays.sort(arr,new Comparator<int>(){
    @Override
    public int compare(int o1,int o2){
        return 0;
    }
});//以传递int数组举例

//lambda表达式改进 大大的好，大大的化简
Arrays.sort(arr,(int o1,int o2)->{
    return o1-o2;
});
//函数式编程，忽略面向对象的复杂语法
//注意：lambda表达式只能简化函数式接口的匿名内部类的书写
//函数式接口：有且只有一个abstract function的接口
//接口上方有注解@FunctionalInterface
//若方法体内只有一行，可以使用lambda的省略写法
Arrays.sort(arr,(o1,o2) -> o1-o2);//比如只想简单逆序
Arrays.sort(arr,(o1,o2) -> o2.length()-o1.length());//字符串按长度逆序排序的例子

底层原理：

匿名内部类简化代码（此为接口实现而非继承关系）
排序方式：插入排序+二分查找
- 默认将0索引的数据当作有序序列，index from 1to last都是无序序列
- 遍历无序的序列得到其每个元素（假设当前遍历得到元素为A）
- 将A往有序序列里插入时，利用二分确定其插入点
- 和插入点元素进行比较的规则就是compare的方法体
- 若方法的返回值为负数，则A继续与前面的数据比较；若正数或0，则跟后面比；直到确定A的最终位置。
compare：
- 形参o1：在无序列表中遍历得到的每个元素
- 形参o2：有序列表中的元素
- 返回值：负数表示当前插入元素较小需放前面；正数表示较大放后面；0表示一样也放后面。
  eg. return o1-o2 // return o2-o1

1. Bookshelf B（入门）2/25

题目描述

Farmer John 最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。
所有 $N(1 \le N \le 20,000)$ 头奶牛都有一个确定的身高 $H_i(1 \le H_i \le 10,000)$。设所有奶牛身高的和为S。书架的高度为 $B$，并且保证 $1 \le B \le S < 2,000,000,007$。
为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不像演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。
显然，塔中的奶牛数目越多，整座塔就越不稳定，于是奶牛们希望在能够到书架顶的前提下，让塔中奶牛的数目尽量少。现在，奶牛们找到了你，希望你帮她们计算这个最小的数目。

没什么好说的，一道简简单单的入门题。我和题解一样思路！原来这就是快排+贪心思想！

import java.util.Scanner;
import java.util.Arrays;
public class Main{
 public static void main(String[] args){
 Scanner sc=new Scanner(System.in);
 //输入
 int n=sc.nextInt();
 int b=sc.nextInt();
 int[] a=new int[n];
 //放进数组
 for(int i=0;i<n;i++){
  a[i]=sc.nextInt();
 }
 //由小到大排序
 Arrays.sort(a);
 //贪心思想：每一次都用最好的奶牛来叠
 int s=0;
 int i=a.length-1;
 int count=0;
 while(s<b){
 count++;
 s+=a[i];
 i--;
 }
 //输出
 System.out.println(count);
 }
}

2. 欢乐的跳（入门）2/25

题目描述

一个 $n$ 个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了 $[1,n-1]$ 之间的所有整数，则称之符合“欢乐的跳”，如数组 ${1,4,2,3}$ 符合“欢乐的跳”，因为差的绝对值分别为：$3,2,1$。
给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

虽然是道入门题，但是因为我扭曲的思路，使我用了几百次各种各样的方法，当然也重新巩固了不少知识。例如快排，例如ArrayList的实用方法等。其实换种思路真的会简单很多。

import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
public class Main{
 public static void main(String[] args){
 Scanner sc=new Scanner(System.in);
 //输入
 int n=sc.nextInt();
 int m=1;
 int[] a=new int[n];
 ArrayList<Integer> b=new ArrayList<>(n-1);
 for(int i=0;i<n;i++){
  a[i]=sc.nextInt();
  if(i<n-1){
   b.add(m);//b数组存储[1,n-1]的所有整数
   m++;
   }
 }
 //计算出绝对值并存储
 int count=0;
 for(int i=0;i<n-1;i++){//以后注意,只要有a[n+1]之类的出现就要i<n-1
  int num=Math.abs(a[i+1]-a[i]);//注意Math.别忘了
  int index=Arrays.binarySearch(b.toArray(),num);//又忘了！二分查找必须有序！！！
  if(index>=0){
  if(num==b.get(index)){
    count++;
    b.remove(index);   
    }
   }
   //System.out.println(num+" "+index+" "+count);
  }
  if(count==n-1)
   System.out.println("Jolly");
  else
   System.out.println("Not jolly");
 }
}

非常的优化代码：

遗憾的是，如果C++用这种方法只能得60分。因为如果差大于1000，那么数组会越界。因为C++定义数组时不能使用变量例如a[n]，数组的大小必须在编译时就确定。
那么令我好奇的是，为什么java就可以呢？以下是一些解释：
C++是一种静态类型语言，需要在编译的时候确定每个变量的类型和大小，因此对于栈分配（在函数内部声明的数组），数组的大小必须是编译时的常量。
而java是一种动态类型语言，所有的数组都是在堆上分配的（new出来的）所以如此。

import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
public class Main{
 public static void main(String[] args){
 Scanner sc=new Scanner(System.in);
 //输入
 int n=sc.nextInt();
 int[] a=new int[n];
 //可以直接使用一个boolean数组来标记这些差值是否出现。
 //不需要使用Arrays.binarySearch来检查差值，直接使用boolean数组的索引即可
 boolean[] b=new boolean[n];
 for(int i=0;i<n;i++){
  a[i]=sc.nextInt();
 }
 //计算出绝对值并标记
 for(int i=0;i<n-1;i++){//以后注意,只要有a[n+1]之类的出现就要i<n-1
     int num=Math.abs(a[i+1]-a[i]);//注意Math.别忘了
     if(num>=1&&num<=n-1)
         b[num]=true;//这样就可以直接避免差值重复的考虑了。要学会用boolean
 }//检查差值是否出现
  boolean flag=true;
  for(int i=1;i<n;i++){
      if(!b[i]){
          flag=false;
          break;
      }
  }
  if(flag)
   System.out.println("Jolly");
  else
   System.out.println("Not jolly");
 }
}

另一种思路：
先把差求出来，再sort，和[1，n-1]做比较，如果不同，直接printf退出，如果一直到最后未能输出，则为欢乐的跳。
和上面的boolean相比，这种方法更加简单直接，排序保证了可以通过简单的线性检查来保证差值的连续性。缺点是增加了额外的计算复杂度，时间复杂度变为O(n logn)。而上面的优化代码时间复杂度仅为O(n)，对于大数据集中处理来说更高效。

int a[1005],c[1005];//定义
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);//读入
    }
    for(int i=1;i<n;i++){
        c[i]=abs(a[i]-a[i+1]);//处理差
    }
    sort(c+1,c+n);
    for(int i=1;i<n;i++){
        if(c[i]!=i){printf("Not jolly\n");return 0;}//判断输出
    }
    printf("Jolly\n");//如果未能输出，则为正确答案
    return 0;//过程结束
}

3. 学生会选举（普及-）2/26

题目描述

学校正在选举学生会成员，有 $n$（$n\le 999$）名候选人，每名候选人编号分别从 $1$ 到 $n$，现在收集到了 $m$（$m \le 2000000$）张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。

虽然用sort可以得分但是TLE和MLE了，需要性能更优秀的算法

import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
public class Main{
 public static void main(String[] args){
 Scanner sc=new Scanner(System.in);
 //输入
 int n=sc.nextInt();
 int m=sc.nextInt();
 int[] a=new int[m];
 for(int i=0;i<m;i++){
 a[i]=sc.nextInt();
 }
 //排序
 Arrays.sort(a);
 //输出
 for(int i=0;i<a.length;i++){
 System.out.print(a[i]+" ");
 }
 }
}

Arrays.sort() 方法在处理基本数据类型数组时使用了双轴快速排序算法，其时间复杂度为 O(n log n)。当 m 非常大时（例如接近2000000），这个排序过程可能会非常慢，导致TLE。此外，程序使用了一个大小为 m 的数组来存储所有的选票编号，这在 m 较大时占用了大量的内存。当 m 接近2000000时，如果每个整数占用4字节，那么仅这个数组就需要大约8MB的内存。如果系统资源有限，这可能会导致内存不足。
所以我想到了另一种方法！

import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
public class Main{
 public static void main(String[] args){
 Scanner sc=new Scanner(System.in);
 //输入
 int n=sc.nextInt();
 int m=sc.nextInt();
 int[] a=new int[n];
 for(int i=0;i<m;i++){
 int vote=sc.nextInt();
 a[vote]++;
 }
 //输出
 for(int i=1;i<a.length;i++){
  for(int j=0;j<a[i];j++){
  System.out.print(i+1+" ");
  }
 }
 }
}

怎么又是两个TLE？不是TLE就是MLE？气死我了
哦哦，我终于知道了！都是m的错！m实在是太大了所以好多地方都需要重新考虑。例如使用了内层循环来输出打印每张选票时非常耗时的，而且每次调用sout方法时都会访问I/O流，这样在逐个输出大量数据时会非常非常慢。
所以优化方法是：使用StringBuilder来构建输出结果然后一次性打印出来，这样可以大幅减少I/O操作的次数。顺利AC！！！

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < m; i++) {
            int index = sc.nextInt();
            a[index - 1]++;
        }
        // 使用 StringBuilder 来构建输出结果
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i]; j++) {
                sb.append(i + 1).append(" ");
            }
        }
        // 输出
        System.out.println(sb.toString());
    }
}

4. 求第k小的数（普及-）2/26

题目描述

输入 $n$（$1 \le n < 5000000$ 且 $n$ 为奇数）个数字 $a_i$（$1 \le a_i < {10}^9$），输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。要求时间复杂度为O(n)

前面的嵌套循环时间复杂度太高了 2TLE QAQ可是难道不用考虑重复的情况么？竟然水过去了60分…

import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
public class Main{
 public static void main(String[] args){
 Scanner sc=new Scanner(System.in);
 //输入
 int n=sc.nextInt();
 int k=sc.nextInt();
 int[] a=new int[n];
 /*for(int i=0;i<n;i++){
  boolean flag=true; 
  int num=sc.nextInt();
  for(int j=0;j<i;j++){
   if(a[j]==num){
    flag=false;
    break;
    }
  }
  if(flag)
   a[i]=num;
 }*/
 for(int i=0;i<n;i++){
 a[i]=sc.nextInt();
 } 
 Arrays.sort(a);
 //输出
 System.out.print(a[k]+" ");
 }
}

于是我打算使用快速选择算法QuickSelect使得平均情况下时间复杂度降为O(n)

import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
public class Main{
 public static void main(String[] args){
 Scanner sc=new Scanner(System.in);
 //输入
 int n=sc.nextInt();
 int k=sc.nextInt();
 int[] a=new int[n];
 for(int i=0;i<n;i++){
     a[i]=sc.nextInt();
 }
 //quick select
 quickSelect(a,0,n-1,k);
 System.out.println(a[k]);
 }
 public static void quickSelect(int[] a,int i,int j,int k){
     int start=i;
     int end=j;
     if(start>=end)
     return;
     int g=a[i];
     while (start!=end){
         while(true){
             if(end<=start||a[end]<g)
             break;
             end--;
         }
         while(true){
             if(end<=start||a[start]>g)
             break;
             start++;
         }
         int tem=a[start];
         a[start]=a[end];
         a[end]=tem;
     }
     int temp=a[i];
     a[i]=a[end];
     a[end]=temp;
     if(end==k)
     return ;
     else if(k<end)
     quickSelect(a,i,start-1,k);
     else
     quickSelect(a,start+1,j,k);
 }
}

啊，为什么还是TLE。我真的要气死了。不管了，60分就60分吧。

5. 明明的随机数（普及-）2/26

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 $N$ 个 $1$ 到 $1000$ 之间的随机整数 $(N\leq100)$，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

抹抹擦擦叽里呱啦改来改去了好久…不知道自己在干什么，又是看错题又是写漏字。。。但是不得不夸一下自己确实有一duidui的进步了！

import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
public class Main{
 public static void main(String[] args){
 Scanner sc=new Scanner(System.in);
 //输入
 int n=sc.nextInt();
 int count=0;
 boolean[] a=new boolean[1001];
 int[] b=new int[n];
 for(int i=0;i<n;i++){
  int index=sc.nextInt();
  if(!a[index]){
  a[index]=true;
  b[count++]=index;}//这里特别特别好！省了一个for还同时避免重复
 }
 Arrays.sort(b,0,count);//避免把0搞进去
 //输出
 System.out.println(count);
 for(int i=0;i<count;i++){
 System.out.print(b[i]+" ");
 }
 }
}

6. 奖学金（普及-）2/26

题目描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 $5$ 名学生发奖学金。期末，每个学生都有 $3$ 门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。
任务：先根据输入的 $3$ 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。

又重新巩固了Comparator看着C++的叽里呱啦题解感觉java终于胜利了一次？哈哈哈

import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Comparator;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        //输入(考虑用用对象？)
        int n=sc.nextInt();
        int[][] a=new int[n][5];
        for(int i=0;i<n;i++){
            a[i][0]=i+1;
            a[i][1]=sc.nextInt();
            a[i][2]=sc.nextInt();
            a[i][3]=sc.nextInt();
            a[i][4]=a[i][1]+a[i][2]+a[i][3];
        }
        //排序
        Arrays.sort(a,(int[] o1,int[] o2)->{
                if(o1[4]!=o2[4])
                    return o2[4]-o1[4];
                else if(o1[1]!=o2[1])
                    return o2[1]-o1[1];
                else
                    return o1[0]-o2[0];
        });
        //输出
        for(int i=0;i<5&&i<n;i++){
            System.out.println(a[i][0]+" "+a[i][4]);
        }
    }
}

7. 宇宙总统（普及-）2/26

题目描述

地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 $n$ 个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。

能有大体思路，想到字符串二维数组很不错！就是Comparator的原理终究还是不太清楚，而且还发现了自己对Debug还是不熟练的问题，出了问题之后好久都没有搞清楚。这道题值得细细深思。

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        //输入
        int n=sc.nextInt();
        String[][] a=new String[n][2];
        for(int i=0;i<n;i++){
        a[i][0]=String.valueOf(i+1);//易出错！
        a[i][1]=sc.next();
        }
        //排序
        Arrays.sort(a,(String[] o1,String[] o2)->{
         if(o1[1].length()!=o2[1].length())
          return o2[1].length()-o1[1].length();
         else
          return o2[1].compareTo(o1[1]);
        });
        //嗯！？难道我出错的原因是比较成编号了？！！！vocal结果还是因为不熟练
        //输出
        System.out.println(a[0][0]);
        System.out.println(a[0][1]);
    }
}

8. 分数线划定（普及-）2/27

题目描述

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的 $150%$ 划定，即如果计划录取 $m$ 名志愿者，则面试分数线为排名第 $m \times 150%$（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。
现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。

WA了好几次。注意认真读题划分步骤，也要注意细节！

import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Comparator;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int count=0;
        int[][] a=new int[n][2];
        for(int i=0;i<n;i++){
            a[i][0]=sc.nextInt();
            a[i][1]=sc.nextInt();
        }
        Arrays.sort(a,(int[] o1,int[] o2)->{
                if(o1[1]!=o2[1])
                return o2[1]-o1[1];
                else
                return o1[0]-o2[0];
            }
        });
        int index=(int)Math.floor(m*1.5)-1;//注意要减1！！
        int score=a[index][1];
        //找到最后一个成绩不低于分数线的选手！
        int finalindex=index;
        while(finalindex<n&&a[finalindex][1]==score){
            finalindex++;
        }
        System.out.print(a[index][1]+" "+finalindex);
        System.out.println();
        for(int i=0;i<finalindex;i++){
            System.out.print(a[i][0]+" "+a[i][1]);
            System.out.println();
        }
    }
}

9. 攀爬者（普及-）2/27

题目描述：

他在地形图上标记了 $N$ 个点，每个点 $P_i$ 都有一个坐标 $(x_i,y_i,z_i)$。所有点对中，高度值 $z$ 不会相等。HKE 准备从最低的点爬到最高的点，他的攀爬满足以下条件：
(1) 经过他标记的每一个点；
(2) 从第二个点开始，他经过的每一个点高度 $z$ 都比上一个点高；
(3) HKE 会飞，他从一个点 $P_i$ 爬到 $P_j$ 的距离为两个点的欧几里得距离。即，$\sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2+(Z_i-Z_j)^2}$
现在，HKE 希望你能求出他攀爬的总距离。

我竟然再java里面看到了C的影子。哈哈。有些易错的小细节一定要注意了！

import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Comparator;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        //输入
        int n=sc.nextInt();
        int[][] a=new int[n][3];
        for(int i=0;i<n;i++){
            a[i][0]=sc.nextInt();
            a[i][1]=sc.nextInt();
            a[i][2]=sc.nextInt();
        }
        //排序
        Arrays.sort(a,(int[] o1,int[] o2)->{
                if(o1[2]!=o2[2])
                return o1[2]-o2[2];
                return 0;
            }
        });
        //临近两数计算并相加
        double sum=0;
        for(int i=0;i<n-1;i++){//注意！！n-1！！
            int x=a[i+1][0]-a[i][0];
            int y=a[i+1][1]-a[i][1];
            int z=a[i+1][2]-a[i][2];
            sum+=Math.sqrt(Math.pow(x,2)+Math.pow(y,2)+Math.pow(z,2));
        }
        //输出
        System.out.printf("%.3f%n",sum);//怎么还有点C的风格呢！
    }
}

10.生日（普及-）2/27

题目描述：

cjf 君想调查学校 OI 组每个同学的生日，并按照年龄从大到小的顺序排序。但 cjf 君最近作业很多，没有时间，所以请你帮她排序。

可恶，竟然只得了32分！哪里出问题了？(昨天和今天刚好都是我的生日哈哈哈）
果然有好多小错误！！输入的日期和索引没有格式化！字符串比较的常见错误！

import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Comparator;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        //输入
        int n=sc.nextInt();
        String[][] a=new String[n][5];
        for(int i=0;i<n;i++){
            a[i][0]=sc.next();
            a[i][1]=sc.next();
            a[i][2]=sc.next();
            a[i][3]=sc.next();
            a[i][4]=String.valueOf(i);
        }
        //排序
        Arrays.sort(a,(String[] o1,String[] o2)->{
                if(!o1[1].equals(o2[1]))
                return o1[1].compareTo(o2[1]);
                else if(!o1[2].equals(o2[2]))
                return o1[2].compareTo(o2[2]);
                else if(!o1[3].equals(o2[3]))
                return o1[3].compareTo(o2[3]);
                else
                return o2[4].compareTo(o1[4]);
            }
        });
        //输出
        for(int i=0;i<n;i++){
            System.out.println(a[i][0]);
        }
    }
}

呜呜呜终于AC了

import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Comparator;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        //输入
        int n=sc.nextInt();
        String[][] a=new String[n][5];
        for(int i=0;i<n;i++){
            a[i][0]=sc.next();
            a[i][1]=sc.next();
            a[i][2]=sc.next();
            a[i][3]=sc.next();
            a[i][4]=String.valueOf(i);
        }
        //排序
        Arrays.sort(a,(String[] o1,String[] o2)->{
                if(!o1[1].equals(o2[1])){
                    if(o1[1].length()==o2[1].length())
                    return o1[1].compareTo(o2[1]);
                    else
                    return o1[1].length()-o2[1].length();
                }
                else if(!o1[2].equals(o2[2])){
                    if(o1[2].length()==o2[2].length())
                    return o1[2].compareTo(o2[2]);
                    else
                    return o1[2].length()-o2[2].length();
                }
                else if(!o1[3].equals(o2[3])){
                    if(o1[3].length()==o2[3].length())
                    return o1[3].compareTo(o2[3]);
                    else
                    return o1[3].length()-o2[3].length();
                }
                else{
                    if(o1[4].length()==o2[4].length())
                    return o2[4].compareTo(o1[4]);
                    else
                    return o2[4].length()-o1[4].length();
                }
        });
        //输出
        for(int i=0;i<n;i++){
            System.out.println(a[i][0]);
        }
    }
}

11.拼数（普及-）2/27

题目描述

设有 $n$ 个正整数 $a_1 \dots a_n$，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

很好的题！使我又发现了好多错误

import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Comparator;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        //输入
        int n=sc.nextInt();
        String[] a=new String[n];
        for(int i=0;i<n;i++){
            a[i]=sc.next();
        }
        //排序
        Arrays.sort(a,(o1,o2)->{
                return (o2+o1).compareTo(o1+o2);//o2和o1的顺序可别错了
            }//非常好！又简洁又避免了“7”与“72”会出现的错误
        });
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<n;i++){
            sb.append(a[i]);
        }
        //输出
        System.out.println(sb.toString());
    }
}