PAT乙级 1065 单身狗 java 测试点34超时

img

img


思路1：创建map对象，把情侣存储进去。随后对于每一位来宾，遍历来宾名单，寻找ta是否有情侣
代码如下：

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

public class Main {

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

        int N=Integer.parseInt(br.readLine());//情侣对数

        //将情侣键值对存储到couple中
        Map<Integer,Integer> couple=new HashMap<>();
        for(int i=1;i<=N;i++){
            String[] ID=br.readLine().split(" ");
            int first=Integer.parseInt(ID[0]);
            int second=Integer.parseInt(ID[1]);

            couple.put(first,second);
        }

        //来宾总数
        int total=Integer.parseInt(br.readLine());

        //来宾名单（int)类型
        int[] guest=new int[total];
        String[] list=br.readLine().split(" ");
        for(int i=0;i<total;i++){
            guest[i]=Integer.parseInt(list[i]);
        }


        int single=total;//单身来宾总数
        //对于每一个来宾，遍历来宾名单，寻找是否有他/她的情侣
        for(int i=0;i<total;i++){
            for(int j=0;j<total;j++){
                Integer coupleID=couple.get(guest[i]);
                Integer search=guest[j];
                if(coupleID==null);

                //如果有，单身人数减2，将该二人的ID设置为-1，表示有情侣在场
                //遍历的同时忽略自身，因为一个人的情侣不会是他/她本人
                else if(coupleID.equals(search)&&i!=j){
                    single-=2;
                    guest[i]= guest[j]=-1;
                }
            }
        }

        Arrays.sort(guest);//升序，题目要求

       out.println(single);
       for(int i=0;i<total;i++){
           if(guest[i]!=-1&&i!=total-1){
               out.print(guest[i]+" ");
           }
           else if(guest[i]!=-1&&i==total-1){
               out.print(guest[i]);
           }
       }
       out.flush();
    }
}
//测试点34超时

这样写复杂度就是o(n^2)，而且题目中给的数据范围很大，所以超时是意料中的。于是我选择换一个写法
思路2：建立两个集合，一个是没有情侣的或者有情侣但是情侣不在场的，另一个是有情侣的集合。遍历有情侣的集合，如果对于某一个ID，ta的情侣不在这个集合中，说明ta是单身狗，要存入第一个集合中。
代码如下：

import java.io.*;
import java.text.DecimalFormat;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        DecimalFormat df = new DecimalFormat("00000");

        in.nextToken();
        int N=(int)in.nval;
        Map<Integer,Integer> couple=new HashMap<>();

        //存储两次，即first的情侣是second且second的情侣是first(题目保证了没有脚踏两条船)
        for(int i=0;i<N;i++){
            in.nextToken();
            int first=(int)in.nval;
            in.nextToken();
            int second=(int)in.nval;

            couple.put(first,second);
            couple.put(second,first);
        }

        in.nextToken();
        int total=(int)in.nval;
        //没有情侣，或者情侣不在场的人，一开始只存没有情侣的人
        Set<Integer> single=new TreeSet<>();
        //有情侣的人，无论有没有情侣在场都存进去
        Set<Integer> hasCouple=new HashSet<>();

        for(int i=0;i<total;i++){
            in.nextToken();
            int ID=(int)in.nval;

            //这个ID有情侣就存进去
            if(couple.containsKey(ID)){
                hasCouple.add(ID);
            }
            //没有就直接存入单身狗集合
            else{
                single.add(ID);
            }
        }

        //如果在场来宾中没有这个ID的情侣，那么存进单身狗名单
        for(Integer ID:hasCouple){
            if(!hasCouple.contains(couple.get(ID))){
                single.add(ID);
            }
        }

        out.println(single.size());
        String result="";
        for(Integer ID:single){
            result+=df.format(ID)+" ";
        }
        out.println(result.trim());
        out.flush();
    }
}

这样写不仅还是测试点34超时，测试点1还出现了格式错误。我查了一下测试点1是没有单身狗，我的运行结果就是0，有什么问题？测试点34超时的问题怎么解决？

img

  1. 将已知的夫妻存入map A中；
  2. 将参加派对的人存入set B中；
  3. 定义存放单身的集合C
  4. for(item : B){
    if(B.contains(A.get(item))){
    continue;
    }else{
    C.add(item);
    }
    }
  5. 输出c的大小，和排序后输出c