题解 | #数据分类处理#

题意整理

• 输入一组整数序列I和一组规则整数序列R。
• 根据条件找出满足规则Ri的I，并按指定格式输出。
• 需要预先对R进行排序和去重，然后对于每一个Ri，找出所有包含Ri的I，依次输出I的个数、I的索引以及I。最后需要在输出结果之前，先输出结果中包含多少整数。

方法一（TreeSet）

1.解题思路

• 首先对规则序列进行排序和去重，处理后的数据放在set中。
• 遍历整个set，对于每一个Ri，记录满足条件的I的个数，以及记录满足条件的I的索引和I。如果I的个数大于0，则将对应的规则数字Ri、I的个数、索引、I加入到res。
• 最后统计整个结果有多少个整数输出。按顺序输出整数个数和res。

图解展示：

2.代码实现

import java.util.Scanner;
import java.util.TreeSet;

public class Main{
    public static void main(String[] args){
        //标准输入
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            //整数序列
            String I=sc.nextLine();
            //规则序列
            String R=sc.nextLine();
            
            //分割为字符串数组
            String[] arrI=I.split(" ");
            String[] arrR=R.split(" ");
            
            //用于去重和排序
            TreeSet<Integer> set=new TreeSet<>();
            
            //遍历规则序列，加入到set
            int m=arrR.length;
            for(int i=1;i<m;i++){
                set.add(Integer.parseInt(arrR[i]));
            }
            
            //记录最终结果
            StringBuilder res=new StringBuilder();
            int n=arrI.length;
            int size=0;
            //遍历去重并排序后的规则序列
            for(Integer Ri:set){
                //记录满足条件的I的个数
                int count=0;
                //记录满足条件的I的索引和I
                StringBuilder sb=new StringBuilder();
                for(int i=1;i<n;i++){
                    //如果包含，则加入到sb
                    if(arrI[i].contains(String.valueOf(Ri))){
                        count++;
                        sb.append(i-1).append(" ");
                        sb.append(arrI[i]).append(" ");
                    }
                }
                if(count>0){
                    //将对应的规则数字Ri、I的个数、索引、I加入到res
                    res.append(Ri).append(" ");
                    res.append(count).append(" ");
                    res.append(sb);
                    //记录整个结果有多少个整数输出
                    size+=count*2+2;
                }
            }
            System.out.println(size+" "+res.toString());
        }
    }
}

3.复杂度分析

• 时间复杂度：假设输入的整数序列长度为m，规则序列的长度为n，需要利用TreeSet对规则进行排序和去重，时间复杂度为$O(nlo{g}_{2}n)O(nlog\_2n)$，之后要遍历每一个规则整数，并在整个原序列中找合适的I，需要两层循环，时间复杂度为$O(n\ast m)O(n*m)$，所以时间复杂度为$O(nlo{g}_{2}n+n\ast m)O(nlog\_2n+n*m)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度是$O(n)O(n)$。

方法二（利用IO）

1.解题思路

与方法一思路基本一致，不过使用io操作处理输入数据。

2.代码实现

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

public class Main{
    public static void main(String[] args) throws Exception{
        //io输入
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        //整数序列
        String I;
        while((I=br.readLine())!=null){
            //规则序列
            String R=br.readLine();
            
            //分割为字符串数组
            String[] arrI=I.split(" ");
            String[] arrR=R.split(" ");
            
            //用于去重和排序
            TreeSet<Integer> set=new TreeSet<>();
            
            //遍历规则序列，加入到set
            int m=arrR.length;
            for(int i=1;i<m;i++){
                set.add(Integer.parseInt(arrR[i]));
            }
            
            //记录最终结果
            StringBuilder res=new StringBuilder();
            int n=arrI.length;
            int size=0;
            //遍历去重并排序后的规则序列
            for(Integer Ri:set){
                //记录满足条件的I的个数
                int count=0;
                //记录满足条件的I的索引和I
                StringBuilder sb=new StringBuilder();
                for(int i=1;i<n;i++){
                    //如果包含，则加入到sb
                    if(arrI[i].contains(String.valueOf(Ri))){
                        count++;
                        sb.append(i-1).append(" ");
                        sb.append(arrI[i]).append(" ");
                    }
                }
                if(count>0){
                    //将对应的规则数字Ri、I的个数、索引、I加入到res
                    res.append(Ri).append(" ");
                    res.append(count).append(" ");
                    res.append(sb);
                    //记录整个结果有多少个整数输出
                    size+=count*2+2;
                }
            }
            System.out.println(size+" "+res.toString());
        }
    }
}

3.复杂度分析

• 时间复杂度：假设输入的整数序列长度为m，规则序列的长度为n，需要利用TreeSet对规则进行排序和去重，时间复杂度为$O(nlo{g}_{2}n)O(nlog\_2n)$，之后要遍历每一个规则整数，并在整个原序列中找合适的I，需要两层循环，时间复杂度为$O(n\ast m)O(n*m)$，所以时间复杂度为$O(nlo{g}_{2}n+n\ast m)O(nlog\_2n+n*m)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度是$O(n)O(n)$。