1028 人口普查 (20分) PAT Java代码实现 -运行超时（牛客AC）

1028 人口普查 (20分)

某城镇进行人口普查，得到了全体居民的生日。现请你写个程序，找出镇上最年长和最年轻的人。

这里确保每个输入的日期都是合法的，但不一定是合理的——假设已知镇上没有超过 200 岁的老人，而今天是 2014 年 9 月 6 日，所以超过 200 岁的生日和未出生的生日都是不合理的，应该被过滤掉。

输入格式：

输入在第一行给出正整数 N，取值在(0,10^5 ]；随后 N 行，每行给出 1 个人的姓名（由不超过 5 个英文字母组成的字符串）、以及按 yyyy/mm/dd（即年/月/日）格式给出的生日。题目保证最年长和最年轻的人没有并列。

输出格式：

在一行中顺序输出有效生日的个数、最年长人和最年轻人的姓名，其间以空格分隔。

输入样例：

5
John 2001/05/12
Tom 1814/09/06
Ann 2121/01/30
James 1814/09/05
Steve 1967/11/20

输出样例：

3 Tom John

解题思路：

此题题意也很容易理解，只需找出在时间段[1814/09/06-2014/09/06]之间的最晚和最早时间。
如何判断时间段是否符合，以及求最大和最小。我刚开始第一想法就是用TreeMap的有序性来排序，后测试发现最后一个测试点运行超时。见下侧代码实现一。
后来考虑可能是TreeMap消耗资源过多，占用内存过大，考虑不存储所有数据，只存储最大最小，动态比较给最大最小变量赋值。发现还是最后一个测试点运行超时。见下侧代码实现二。
又考虑String的compareTo()方法效率低，将其转换为int 类型直接比较。还是最后一个测试点运行超时。 见下侧代码实现三。

坑一： 刚开始是以为考察重点是求200年前具体年月日，后通过观察测试用例发现不是这样。
坑二： 若所有数据都不符合规则，则应只输出 0
坑三： 若数据只有一条，年纪最大和最小都应输出同一个人名，即打印两个相同的名字。

最后一个测试点未过，运行超时，得分16。试了好几种方法还是运行超时，心态不好了。求大佬解答。

代码实现一：

利用TreeMap的有序性来排序

import java.util.Collection;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        //读取输入
        Scanner sc = new Scanner(System.in);
        //要输入的数量  10的5次方属于int范围
        int number = sc.nextInt();
        //nextLine()返回类型为String(字符串对象)，返回一整行。会读取回车换行符。
        //此处是为了读取回车换行符
        sc.nextLine();
        //最大日期字符串，超过这个日期为非法
        String max = "2014/09/06";
        //最小日期字符串，小于这个日期为非法
        String min = "1814/09/06";
        //TreeMap 是一个有序的key-value集合，通过红黑树实现的。
        Map<String,String> map = new TreeMap<>();
        //循环读取输入的数据
        for(int x = 0; x < number; x++){
            //读取姓名和日期
            String[] data = sc.nextLine().split(" ");
            //将符合条件的数据放进map中排序
            if(data[1].compareTo(min) >= 0 && data[1].compareTo(max) <= 0 ){
                // 利用其有序特性，将日期作为key排序，人名作为value
                map.put(data[1],data[0]);
            }
        }
        //所有数据都无效 仅仅打印0且不带空格和换行
        if(map.size() == 0){
            System.out.print("0");
        }else{
            //合格数据的数量为map的大小
            System.out.print(map.size() + " ");
            //map中第一个为最年长 最后一个为最年轻
            Object[] values = map.values().toArray();
            System.out.print(values[0] + " ");
            System.out.print(values[values.length-1]);
        }
    }
}

代码实现二：

动态比较给最大最小变量赋值

import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        //读取输入
        Scanner sc = new Scanner(System.in);
        //要输入的数量  10的5次方属于int范围
        int number = sc.nextInt();
        //nextLine()返回类型为String(字符串对象)，返回一整行。会读取回车换行符。
        //此处是为了读取回车换行符
        sc.nextLine();
        //最大日期字符串，超过这个日期为非法
        String max = "1814/09/06";
        //最小日期字符串，小于这个日期为非法
        String min = "2014/09/06";
        //计数
        int count = 0;
        //存储年龄最大和最小的名字
        String maxName = "";
        String minName = "";
		//循环读取数据
        for(int x = 0; x < number; x++){
            //读取姓名和日期
            String[] data = sc.nextLine().split(" ");
            //将符合条件的数据放进map中排序
            if(data[1].compareTo("1814/09/06") >= 0 && data[1].compareTo("2014/09/06") <= 0 ){
                // 利用其有序特性，将日期作为key排序，人名作为value
                count++;     
                if(data[1].compareTo(max) >= 0){
                    max = data[1];
                    maxName = data[0];
                }
                if(data[1].compareTo(min) <= 0){
                    min = data[1];
                    minName = data[0];
                }
            }
        }
        //日期最大的为年龄最小的
        if(count == 0){
            System.out.print("0");
        }else{
            System.out.print(count + " ");
            System.out.print(minName + " ");
            System.out.print(maxName );
        }
    }
}

代码实现三：

动态比较给最大最小变量赋值

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //读取输入
        Scanner sc = new Scanner(System.in);
        //要输入的数量  10的5次方属于int范围
        int number = sc.nextInt();
        //nextLine()返回类型为String(字符串对象)，返回一整行。会读取回车换行符。
        //此处是为了读取回车换行符
        sc.nextLine();
        //最大日期字符串，超过这个日期为非法
        int max = 18140906;
        //最小日期字符串，小于这个日期为非法
        int min = 20140906;
        //计数
        int count = 0;
        //暂存人名
        String maxName = "";
        String minName = "";
        //循环读取处理
        for(int x = 0; x < number; x++){
            //读取姓名和日期
            String[] data = sc.nextLine().split(" ");
            //转为int类型
            int date = Integer.parseInt(data[1].replaceAll("/",""));
            if(date >= 18140906 && date <= 20140906){
                //计数
                count++;
                //和最小的值比较
                if(date >= max){
                    max = date;
                    maxName = data[0];
                }
                //和最大的值比较
                if(date <= min){
                    min = date;
                    minName = data[0];
                }
            }
        }
        //日期最大的为年龄最小的
        if(count == 0){
            System.out.print("0");
        }else{
            System.out.print(count + " ");
            System.out.print(minName + " ");
            System.out.print(maxName );
        }
    }
}