题目主要信息

1、 一组输入整数序列I和一组规则整数序列R，I和R序列的第一个整数为序列的个数（个数不包含第一个整数）；整数范围为0~(2^31)-1，序列个数不限

2、 从R依次中取出R[i]，对I进行处理，找到满足条件的I

3、按R[i]从小到大的顺序:

(1)先输出R[i]；

(2)再输出满足条件的I的个数；

(3)然后输出满足条件的I在I序列中的位置索引(从0开始)；

(4)最后再输出I。

4、附加条件：

(1)R[i]需要从小到大排序。相同的R[i]只需要输出索引小的以及满足条件的I，索引大的需要过滤掉

(2)如果没有满足条件的I，对应的R[i]不用输出

(3)最后需要在输出序列的第一个整数位置记录后续整数序列的个数(不包含“个数”本身)

方法一：直接暴力求解

具体方法

遍历每个R[i]，并遍历每个I[i]是否符合要求，符合的话就记录。

Java代码

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));
        String str;
        while ((str = br.readLine()) != null) {
            if (str.equals("")) continue;
            //需要过了的I
            String[] I = str.split(" ");
            // R
            String[] temp = br.readLine().split(" ");
            long[] R = new long[Integer.parseInt(temp[0])];
            for (int i = 0; i < R.length; i++) R[i] = Long.parseLong(temp[i+1]);
            //先对R进行排序 然后在依次遍历
            Arrays.sort(R);
            //最终的结果记录 
            StringBuilder result = new StringBuilder();
            int count = 0;
            for (int i = 0; i < R.length; i++) {
                //当R中的值相等的时候 只保留第一个出现的 
                if (i > 0 && R[i] == R[i-1]) continue;
                //需要进行匹配的字符 
                String pattern = R[i] + "";
                int num = 0;
                StringBuilder index = new StringBuilder();
                for (int j = 1; j < I.length; j++) {
                    //说明出现了 找到位置
                    if (I[j].indexOf(pattern) != -1) {
                        num++;
                        index.append(" ").append(j-1).append(" ").append(I[j]);
                    }
                }
                //说明存在跟此时R[i]匹配的I
                if (num > 0){
                    result.append(" ").append(R[i]).append(" ").append(num).append(index);
                    count += num*2+2;
                }
            }
            System.out.println(count + result.toString());
        }
    }
}

复杂度分析

• 时间复杂度：$O(nm+mlogm)O(nm+mlogm)$，需要两层for循环遍历，一层遍历R一层遍历I，另外就是进行了排序的操作。
• 空间复杂度：$O(1)O(1)$ ,都是常数级别变量

方法二：借助Map

具体做法

在每一轮遍历I的过程中，将当前I[i]存入到Map中，并以key和value的形式，其中key是当前元素的下标，value为当前元素的值。

最终在遍历Map,将结果存入到最终的result结果中。

Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int num = sc.nextInt();
            //读取I
            String[] array = new String[num];
            for (int i =0; i<num; i++) {
                array[i] = String.valueOf(sc.nextInt());
            }
            //读取R
            int rnum = sc.nextInt();
            Set<Integer> set = new TreeSet<>();
            for (int i =0; i<rnum; i++) {
                set.add(sc.nextInt());
            }


            StringBuilder result = new StringBuilder();
            int count = 0;//记录符合的个数
            //遍历 R
            for (int i : set) {
                int j = 0;//记录I的每个元素的index
                Map<Integer, String> map = new TreeMap<>();
                //在I中寻找符合要求的I[i]
                for (String str : array) {
                    if (str.contains(String.valueOf(i))){
                        map.put(j, str);
                    }
                    j++;
                }
                //如果Map非空 则存入result中 
                if (!map.isEmpty()) {
                    if (count > 0) {
                        result.append(" ");
                    }
                    result.append(i).append(" ").append(map.size());
                    count +=2;//多两个数组 
                    for (Map.Entry<Integer, String> entry : map.entrySet()) {
                        count+=2;
                        result.append(" ").append(entry.getKey()).append(" ").append(entry.getValue());
                    };
                }
            }
            if (count > 0) {
                StringBuilder result2 = new StringBuilder();
                result2.append(count).append(" ").append(result.toString());
                System.out.println(result2.toString());
            }
        }
    }
}

复杂度分析

• 时间复杂度：$O(nm+mlog2m)O(nm+mlog2m)$，需要两层for循环遍历，一层遍历R一层遍历I，另外就是进行了排序的操作。

• 空间复杂度：$O(n)O(n)$，辅助空间为哈希表的长度.