一道PAT1100 校庆 运行超时

Question

我的思路是 先读取所有数据，遍历两个数组，然后创建数组用来存储实际到场的校友的ID，然后根据校友到场人数查询相应数组，遍历数组输出年龄最大的人
但是自己写的时候也意识到暴力很容易超时，但还是没能想出来优化的方法，最终两个测试点超时
代码如下：

import java.io.*;

public class Main{

    //找年龄最大的方法
    public static String FindOldest(String[] list){
        int max=99999999;
        String maxID="";
        for(String info:list) {
            if (info != null) {
                int date = Integer.parseInt(info.substring(6, 14));
                if (date < max) {
                    max = date;
                    maxID = info;
                }
            }
        }
        return maxID;
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //校友数组
        int N=Integer.parseInt(br.readLine());
        String[] alumni=new String[N];
        for(int i=0;i<N;i++){
            alumni[i]=br.readLine();
        }

        //来宾数组
        int M=Integer.parseInt(br.readLine());
        String[] guest=new String[M];
        for(int i=0;i<M;i++){
            guest[i]=br.readLine();
        }

        //实到校友计数器和数组
        int count=0;
        String[] alumniGuest=new String[N];

        //遍历来宾数组和校友数组 发现同ID存入实到数组
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(guest[i].equals(alumni[j])){
                    count++;
                    alumniGuest[j]=alumni[j];
                    break;
                }
            }
        }

        //最终输出
        String Oldest="";

        //题目要求
        if(count!=0){
            Oldest=FindOldest(alumniGuest);
        }
        if(count==0){
            Oldest=FindOldest(guest);
        }

        System.out.println(count);
        System.out.println(Oldest);

    }
}

最终测试点三四超时，请问具体怎么解决？

Answer 1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class Demo {
//找年龄最大的ID
private static String getMaxID(Map<String,Integer> map){
int max=Integer.MAX_VALUE;
String maxID="";
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()){
Map.Entry<String, Integer> next = iterator.next();
if(max>next.getValue()){
max = next.getValue();
maxID = next.getKey();
}
}
return maxID;
}

public static void main(String[] args) throws IOException {
    InputStreamReader inputStreamReader = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(inputStreamReader);
    String key="";
    Map<String,Integer> alumni = new HashMap<>();//校友集合
    Map<String,Integer> guest = new HashMap<>();//来宾集合
    Map<String,Integer> alumniGuest = new HashMap<>();////实到校友集合

    int N=Integer.parseInt(br.readLine());
    for (int i = 0; i < N; i++) {
        key = br.readLine();
        alumni.put(key,Integer.parseInt(key.substring(6,14)));
    }

    int M=Integer.parseInt(br.readLine());
    for (int i = 0; i < M; i++) {
        key = br.readLine();
        guest.put(key,Integer.parseInt(key.substring(6,14)));
        if(alumni.containsKey(key)){
            alumniGuest.put(key,Integer.parseInt(key.substring(6,14)));
        }
    }

    System.out.println(alumniGuest.size());

    if(alumniGuest.size()==0){//没有校友来
        System.out.println(getMaxID(guest));
    }else {//有校友来
        System.out.println(getMaxID(alumniGuest));
    }
    inputStreamReader.close();
    br.close();

}

}