描述现在有很多长方形，每一个长方形都有一个编号，这个编号可以重复；还知道这个长方形的宽和长，编号、长、宽都是整数；现在要求按照一下方式排序（默认排序规则都是从小到大）；

1.按照编号从小到大排序

2.对于编号相等的长方形，按照长方形的长排序；

3.如果编号和长都相同，按照长方形的宽排序；

4.如果编号、长、宽都相同，就只保留一个长方形用于排序,删除多余的长方形；最后排好序按照指定格式显示所有的长方形；

输入

第一行有一个整数 0<n<10000,表示接下来有n组测试数据；
每一组第一行有一个整数 0<m<1000，表示有m个长方形；
接下来的m行，每一行有三个数 ，第一个数表示长方形的编号，

第二个和第三个数值大的表示长，数值小的表示宽，相等
说明这是一个正方形（数据约定长宽与编号都小于10000）；

输出

顺序输出每组数据的所有符合条件的长方形的 编号 长 宽

样例输入

181 1 11 1 11 1 21 2 11 2 22 1 12 1 22 2 1

样例输出

1 1 11 2 11 2 22 1 12 2 1


思路：先对长和宽进行排序，在根据编号，边长，宽排序

import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main{public static void main(String arg[]) throws Exception{InputStreamReader is=new InputStreamReader(System.in);BufferedReader bf=new BufferedReader(is);Integer n=Integer.valueOf(bf.readLine());while(n>0){n--;Integer m=Integer.valueOf(bf.readLine());Integer[][] a=new Integer[m][3];for(int i=0;i<m;i++){String ln=bf.readLine();String[] line=ln.split(" ");Integer aa=Integer.valueOf(line[2]);Integer bb=Integer.valueOf(line[1]);if(aa>bb){Integer temp=aa;aa=bb;bb=temp;}a[i][0]=Integer.valueOf(line[0]);a[i][1]=bb;a[i][2]=aa;for(int j=i;j>0;j--){if(a[j][0]<a[j-1][0]){Integer[] num=a[j-1];a[j-1]=a[j];a[j]=num;}else if(a[j][0]==a[j-1][0]){if(a[j][1]<a[j-1][1]){Integer[] num=a[j-1];a[j-1]=a[j];a[j]=num;}else if(a[j][1]==a[j-1][1]){if(a[j][2]<a[j-1][2]){Integer[] num=a[j-1];a[j-1]=a[j];a[j]=num;}else if(a[j][2]==a[j-1][2]){a[j][0]=10001;}}}}}//String s=Arrays.toString(a[n][3]).replace("[","").replace("]","").replaceAll(","," ");//Systemfor(int x=0;x<m;x++){if(a[x][0]==10001){continue;}System.out.println(a[x][0]+" "+a[x][1]+" "+a[x][2]);}}}} 

程序没验证通过，不知道问题出在哪里，之后查看网上别人的代码，

把每个长方形看出一个对象，这个对象保护编号（id），长（length），宽（width）

使用hashset去重，之后转成list 使用comparator.sort 方法排序

import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.HashSet;import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int n = Integer.parseInt(sc.nextLine());        while (n-- != 0) {            int m = Integer.parseInt(sc.nextLine());            HashSet<Rect> set = new HashSet<Rect>();            for (int i=0; i < m; i++){                String str = sc.nextLine();                String s[] = str.split(" ");                int length = Math.max(Integer.parseInt(s[1]), Integer.parseInt(s[2]));                int width = Math.min(Integer.parseInt(s[1]), Integer.parseInt(s[2]));                Rect rect = new Rect(Integer.parseInt(s[0]), length, width);                set.add(rect);            }            ArrayList<Rect> list = new ArrayList<Rect>(set);            Collections.sort(list, new MyComparator());            for (Rect rect : list){                System.out.println(rect.id + " " + rect.length + " " + rect.width);            }        }    }}class MyComparator implements Comparator<Rect>{    @Override    public int compare(Rect arg0, Rect arg1) {        if (arg0.id != arg1.id){            return arg0.id - arg1.id;        }else if (arg0.length != arg1.length){            return arg0.length - arg1.length;        }else{            return arg0.width - arg1.width;        }    }    }class Rect {    int id;    int length;    int width;    public Rect(int id, int length, int width) {        this.id = id;        this.length = length;        this.width = width;    }    public int hashCode() {        final int prime = 31;        int result = 1;        result = prime * result + id;        result = prime * result + length;        result = prime * result + width;        return result;    }    public boolean equals(Object obj) {        if (this == obj) {            return true;        }        if (obj == null) {            return false;        }        if (getClass() != obj.getClass()) {            return false;        }        Rect other = (Rect) obj;        if (id != other.id) {            return false;        }        if (length != other.length) {            return false;        }        if (width != other.width) {            return false;        }        return true;    }}

然后我根据这个思路，自己也写个程序

import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.HashSet;import java.util.Scanner;public class text1 {    /**     * @param args     */    public static void main(String[] args) {        Scanner sn=new Scanner(System.in);        Integer n=Integer.valueOf(sn.nextLine());        while(n-->0){            Integer m=Integer.valueOf(sn.nextLine());            HashSet<Rect> set=new HashSet<Rect>();            for(int i=0;i<m;i++){                String[] ln=sn.nextLine().split(" ");                Rect r=new Rect();                r.setLength(Math.max(Integer.valueOf(ln[1]),Integer.valueOf(ln[2])));                r.setWidth(Math.min(Integer.valueOf(ln[1]),Integer.valueOf(ln[2])));                r.setNum(Integer.valueOf(ln[0]));                set.add(r);            }            ArrayList<Rect> r1=new ArrayList<Rect>(set);            Collections.sort(r1, new MyComparator());            for(Rect rec:r1){                System.out.println(rec.getNum()+" "+rec.getLength()+" "+rec.getWidth());            }        }    }    }public class MyComparator implements Comparator<Rect>{    @Override    public int compare(Rect o1, Rect o2) {        // TODO Auto-generated method stub        if(!o1.getNum().equals(o2.getNum())){            return o1.getNum()-o2.getNum();        }        if(!o1.getLength().equals(o2.getLength())){            return o1.getLength()-o2.getLength();        }        if(!o1.getWidth().equals(o2.getWidth())){            return o1.getWidth()-o2.getWidth();        }        return 0;    }            }    class Rect{    private Integer length;    private Integer width;    private Integer num;        public void setNum(Integer num) {        this.num = num;    }    public Integer getNum() {        return num;    }    @Override    public int hashCode() {        final int prime = 31;        int result = 1;        result = prime * result + ((length == null) ? 0 : length.hashCode());        result = prime * result + ((num == null) ? 0 : num.hashCode());        result = prime * result + ((width == null) ? 0 : width.hashCode());        return result;    }    @Override    public boolean equals(Object obj) {        if (this == obj)            return true;        if (obj == null)            return false;        if (getClass() != obj.getClass())            return false;        Rect other = (Rect) obj;        if (length == null) {            if (other.length != null)                return false;        } else if (!length.equals(other.length))            return false;        if (num == null) {            if (other.num != null)                return false;        } else if (!num.equals(other.num))            return false;        if (width == null) {            if (other.width != null)                return false;        } else if (!width.equals(other.width))            return false;        return true;    }    public Integer getWidth(){        return width;    }    public void setWidth(Integer width){        this.width=width;    }    public void setLength(Integer length) {        this.length = length;    }    public Integer getLength() {        return length;    }}

通过了。

 

但是我发现，我的时间，空间复杂度都别网上的大

网上的耗时 118 占内存827

我的 131 1019

对比发现，定义Rect（）类有所差别，之后，我使用它的Rect类，运行之后106 885 

说明这两种方式定义的class类占用你的内存不一样，不明白为什么。

总结：今天这ACM题给我最大的感触就是，用java编程，就多用面向对象的思路去解题，之后的ACM题中，我会尝试着使用设计模式去解题。

一种排序