刷题笔记-（牛客NC24743）[USACO 2010 Nov B]Race Results（比赛结果）-自定义类排序

本文最后更新于：December 3, 2021 pm

积土成山，风雨兴焉；积水成渊，蛟龙生焉；积善成德，而神明自得，圣心备焉。故不积跬步，无以至千里，不积小流无以成江海。齐骥一跃，不能十步，驽马十驾，功不在舍。面对悬崖峭壁，一百年也看不出一条裂缝来，但用斧凿，能进一寸进一寸，能进一尺进一尺，不断积累，飞跃必来，突破随之。

题目

翻译为中文（浏览器翻译）：
牛群跑了第一场马拉松！N (1 <= N <= 5,000) 次已以小时 (0 <= 小时 <= 99)、分钟 (0 <= 分钟 <= 59) 和秒 (0 <= 秒 <= 59)。Bessie 必须将它们（按小时、分钟和秒）按升序排序，最小的时间在前。具体题目见链接。

题目链接

输入描述：

第 1 行：单个整数：N
第 2..N+1 行：第 i+1 行包含奶牛 i 的时间，以三个空格分隔的整数表示：小时、分钟、秒

输出描述：

Lines 1..N：每行包含一个牛的时间，作为三个空格分隔的整数

示例：

//in
3 
11 20 20 
11 15 12 
14 20 14
//out
11 15 12 
11 20 20 
14 20 14


考虑一个简单的例子，它来自一个只有 3 头奶牛的小群（注意，奶牛不会跑 26.2 英里那么快）
：
    11 : 
    20 : 20 
    11:15:12 
    14:20:14正确的排序结果是：11 :15:12 
    11:20:20 
    14:20:14

这道题就是类似于给一个类（结构体）排序。题很简单，主要是记录Java中的自定义类排序的实现。

AC代码：


import java.io.*;
import java.util.*;

/**
 * @Author DragonOne
 * @Date 2021/9/4 19:40
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner Scin = new Scanner(System.in);
        StreamTokenizer STcin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        BufferedReader BRcin = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        
        List<NBB> list = new ArrayList<>();
        int t;
        t = Scin.nextInt();
        for (int i = 0; i < t; i++) {
            NBB nbb = new NBB();
            int h = Scin.nextInt();
            nbb.setH(h);
            int m = Scin.nextInt();
            nbb.setM(m);
            int s = Scin.nextInt();
            nbb.setS(s);
            list.add(nbb);
        }
        Collections.sort(list, new cmp());
        for(NBB it : list){
            out.println(it.getH()+" "+it.getM()+ " "+ it.getS());
            out.flush();
        }
    }

    public static class NBB {
        public NBB() {
        }
        int h;
        int m;
        int s;
        @Override
        public String toString() {
            return "NBB{" +
                    "h=" + h +
                    ", m=" + m +
                    ", s=" + s +
                    '}';
        }

        public int getH() {
            return h;
        }
        public void setH(int h) {
            this.h = h;
        }
        public int getM() {
            return m;
        }
        public void setM(int m) {
            this.m = m;
        }
        public int getS() {
            return s;
        }
        public void setS(int s) {
            this.s = s;
        }
        public NBB(int h, int m, int s) {
            this.h = h;
            this.m = m;
            this.s = s;
        }
    }

    static class cmp implements Comparator {
        @Override
        public int compare(Object o1, Object o2) {
            NBB t1 = (NBB) o1;
            NBB t2 = (NBB) o2;
            if (t1.getH() < t2.getH()) {
                return -1;
            } else if (t1.getH() > t2.getH()) {
                return 1;
            } else {
                if (t1.getM() < t2.getM()) {
                    return -1;
                } else if (t1.getM() > t2.getM()) {
                    return 1;
                } else {
                    if (t1.getS() < t2.getS()) {
                        return -1;
                    } else if (t1.getS() > t2.getS()) {
                        return 1;
                    } else {
                        return 0;
                    }
                }
            }
        }
    }
}

总结

关于Java中给自定义类排序，有两种方法。通过实现 Comparable 或者 Comparator来完成。

1.Comparator

自定义简单的Comparator中compare方法（用于比较器）。
首先，需要知道返回值代表什么，如下：

int compare(Object o1, Object o2) 返回一个基本类型的整型

如果要按照升序排序
则o1 小于o2，返回-1（负数），相等返回0，01大于02返回1（正数）
如果要按照降序排序
则o1 小于o2，返回1（正数），相等返回0，01大于02返回-1（负数）

总结：如果符合条件，则返回-1（负数），不符合返回1（正数），相等返回0。

例如，本题中的自定义排序为升序排序：

static class cmp implements Comparator {
        @Override
        public int compare(Object o1, Object o2) {
            NBB t1 = (NBB) o1;
            NBB t2 = (NBB) o2;
            if (t1.getH() < t2.getH()) { //符合排序条件
                return -1;
            } else if (t1.getH() > t2.getH()) { //不符合排序条件
                return 1;
            } else { //相等的情况下
                if (t1.getM() < t2.getM()) {
                    return -1;
                } else if (t1.getM() > t2.getM()) {
                    return 1;
                } else {
                    if (t1.getS() < t2.getS()) {
                        return -1;
                    } else if (t1.getS() > t2.getS()) {
                        return 1;
                    } else {
                        return 0;
                    }
                }
            }
        }
    }

📢注意：这里也可以直接使用类中成员。如下：

static class cmp implements Comparator {
        @Override
        public int compare(Object o1, Object o2) {
            NBB t1 = (NBB) o1;
            NBB t2 = (NBB) o2;
            if (t1.h < t2.h ) {
                return -1;
            } else if (t1.h  > t2.h ) {
                return 1;
            } else {
                if (t1.m < t2.m) {
                    return -1;
                } else if (t1.m > t2.m) {
                    return 1;
                } else {
                    if (t1.s < t2.s) {
                        return -1;
                    } else if (t1.s > t2.s) {
                        return 1;
                    } else {
                        return 0;
                    }
                }
            }
        }
    }

其中，也可以自定义比较类型，如下：

static class cmp implements Comparator<NBB> {
        @Override
        public int compare(NBB o1, NBB o2) {
            NBB t1 = (NBB) o1;
            NBB t2 = (NBB) o2;
            if (t1.h < t2.h ) {
                return -1;
            } else if (t1.h  > t2.h ) {
                return 1;
            } else {
                if (t1.m < t2.m) {
                    return -1;
                } else if (t1.m > t2.m) {
                    return 1;
                } else {
                    if (t1.s < t2.s) {
                        return -1;
                    } else if (t1.s > t2.s) {
                        return 1;
                    } else {
                        return 0;
                    }
                }
            }
        }
    }

2.Comparable

题目的AC代码：


import java.io.*;
import java.util.*;

/**
 * @Author DragonOne
 * @Date 2021/9/4 19:40
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner Scin = new Scanner(System.in);
        StreamTokenizer STcin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        BufferedReader BRcin = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        List<NBB> list = new ArrayList<>();
        int t;
        t = Scin.nextInt();
        for (int i = 0; i < t; i++) {
            NBB nbb = new NBB();
            int h = Scin.nextInt();
            nbb.setH(h);
            int m = Scin.nextInt();
            nbb.setM(m);
            int s = Scin.nextInt();
            nbb.setS(s);
            list.add(nbb);
        }
        Collections.sort(list);
        for (NBB it : list) {
            out.println(it.getH() + " " + it.getM() + " " + it.getS());
            out.flush();
        }
    }

    public static class NBB implements Comparable {
        public NBB() {
        }
        public int h;
        public int m;
        public int s;
        @Override
        public String toString() {
            return "NBB{" +
                    "h=" + h +
                    ", m=" + m +
                    ", s=" + s +
                    '}';
        }
        public int getH() {
            return h;
        }
        public void setH(int h) {
            this.h = h;
        }
        public int getM() {
            return m;
        }
        public void setM(int m) {
            this.m = m;
        }
        public int getS() {
            return s;
        }
        public void setS(int s) {
            this.s = s;
        }
        public NBB(int h, int m, int s) {
            this.h = h;
            this.m = m;
            this.s = s;
        }
        @Override
        public int compareTo(Object O) {
            NBB o = (NBB) O;
            if (this.h < o.h) {
                return -1;
            } else if (this.h > o.h) {
                return 1;
            } else {
                if (this.m < o.m) {
                    return -1;
                } else if (this.m > o.m) {
                    return 1;
                } else {
                    if (this.s < o.s) {
                        return -1;
                    } else if (this.s > o.s) {
                        return 1;
                    } else {
                        return 0;
                    }
                }
            }
        }
    }

}

主要代码：

@Override
        public int compareTo(Object O) {
            NBB o = (NBB) O;
            if (this.h < o.h) {
                return -1;
            } else if (this.h > o.h) {
                return 1;
            } else {
                if (this.m < o.m) {
                    return -1;
                } else if (this.m > o.m) {
                    return 1;
                } else {
                    if (this.s < o.s) {
                        return -1;
                    } else if (this.s > o.s) {
                        return 1;
                    } else {
                        return 0;
                    }
                }
            }
        }

📢扩展：如果需要Arrays.sort中也是自定义排序，具体做法和Comparable一样，在类内部进行的。

1.3 区别

Comparable和Comparator都是用来实现集合中元素的比较、排序的，只是Comparable是在集合内部定义的方法实现的排序，Comparator是在集合外部实现的排序，所以想要实现排序，就需要在集合外定义Comparator接口或在集合内实现Comparable接口两种方法。
Comparable实现的排序只能是自然排序，这里的自然顺序就是实现Comparable接口设定的排序方式（Demo是按照年龄从小到大排序）。而Comparator是一个专用的比较器，当这个对象不支持自比较或者自比较函数不能满足你的要求时，你可以写一个比较器来完成两个对象之间大小的比较。
Comparable是在集合内部定义的方法实现的排序，位于java.lang下，而Comparator是在集合外部实现的排序，位于java.util。comparable相当于内部比较器。comparator相当于外部比较器。一般情况下，仅用于比较时，可用comparator这个外部比较器，如果想让类支持排序，或者更复杂的排序使用Comparable比较多些。具体可根据实际情况具体应用。

刷题笔记

本文作者: 墨水记忆
本文链接: https://tothefor.com/DragonOne/3866321242.html
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

刷题笔记-（洛谷）二进制位互换 Previous

刷题笔记-（牛客NC54287）红鲤鱼与绿鲤鱼与驴-输入问题 Next