题目的主要信息：

输入整数序列I和规则整数序列R。对于R中的每一个元素，输出:

$R < i >$ ，需要去重和排序。
包含 $R < i >$ 的I中元素的个数
包含 $R < i >$ 的I中元素的值
I中元素的索引

方法一：

逐个输入I，用string类型存储，便于用find函数查找。R需要去重，因此用集合保存。主要用到了四个变量，用count保存满足条件的I中元素个数；index满足条件的I的位置索引；value满足条件的I ；num保存排序好的R中元素。用iterator遍历集合，用find函数判断I中元素是否含有R中元素（iterator是按大小顺序遍历的），在I中找到符合的值，更新四个变量。最后输出。

alt 具体做法：

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    int m, n;
    while(cin >> m) {//逐个输入I
        vector<string> I(m);//string便于用find函数查找
        for(int i = 0; i < m; i++) {
            cin >> I[i];
        }
        cin >> n;
        set<int> R;//需要去重，因此用集合保存R
        for(int i = 0; i < n; i++) {//逐个输入R
            int temp;
            cin >> temp;
            R.insert(temp);
        }
        vector<int> count;//保存R<i>的满足条件的个数
        vector<int> index;//满足条件的I的位置索引
        vector<string> value;//满足条件的I
        vector<int> num;//排序好的R<i>
        for(auto iter = R.begin(); iter != R.end(); iter++) {//用iterator遍历是按大小顺序遍历的，省去排序步骤
            int cnt = 0;
            for(int i = 0; i < m; i++) {//在I中找到符合的值
                if (I[i].find(to_string(*iter)) != I[i].npos) {
                    cnt++;
                    index.push_back(i);//保存索引
                    value.push_back(I[i]);//保存值
                }
            }
            if (cnt != 0) {
                count.push_back(cnt);
                num.push_back(*iter);
            }
        }
        //输出总个数
        cout << num.size() + index.size() + value.size() + count.size() << " ";
        int i,j=0;
        int sum = 0;
        for(i = 0; i < num.size(); i++) {
            cout << num[i] << " " << count[i] << " ";
            sum += count[i];
            while(sum){//输出满足条件的I的索引和值
                if (i == num.size() - 1 && j == index.size() - 1) {
                    cout << index[j] << " "<< value[j] << endl;
                } else {
                    cout << index[j] << " "<< value[j] << " ";
                }
                sum--;
                j++;
            }
        }
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (m n)$ ，外部循环遍历R，内部循环遍历I。
空间复杂度： $O (m + n)$ ，count的长度为n，value的长度为m。

方法二：

整体思路和方法一相同，但是不采用集合set，用普通的vector存储。那么就需要对R进行排序和去重的操作。

排序：用sort函数排序。
去重：遍历R时，由于已经排序过了，如果当前值和前一个值相同，则表示重复，继续遍历下一个。

具体做法：

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    int m, n;
    while(cin >> m) {//逐个输入I
        vector<string> I(m);//string便于用find函数查找
        for(int i = 0; i < m; i++) {
            cin >> I[i];
        }
        cin >> n;
        vector<int> R(n);//保存R
        for(int i = 0; i < n; i++) {//逐个输入R
            cin >> R[i];
        }
        sort(R.begin(), R.end());//排序
        vector<int> count;//保存R<i>的满足条件的个数
        vector<int> index;//满足条件的I的位置索引
        vector<string> value;//满足条件的I
        vector<int> num;//保存满足条件的R<i>
        for(int i = 0; i < R.size(); i++) {
            if(i != 0 && R[i] == R[i-1]) continue;//去重
            int cnt = 0;
            for(int j = 0; j < m; j++) {//在I中找到符合的值
                if (I[j].find(to_string(R[i])) != I[j].npos) {
                    cnt++;
                    index.push_back(j);//保存索引
                    value.push_back(I[j]);//保存值
                }
            }
            if (cnt != 0) {
                count.push_back(cnt);
                num.push_back(R[i]);
            }
        }
        //输出总个数
        cout << num.size() + index.size() + value.size() + count.size() << " ";
        int i,j=0;
        int sum = 0;
        for(i = 0; i < num.size(); i++) {
            cout << num[i] << " " << count[i] << " ";
            sum += count[i];
            while(sum){//输出满足条件的I的索引和值
                if (i == num.size() - 1 && j == index.size() - 1) {
                    cout << index[j] << " "<< value[j] << endl;
                } else {
                    cout << index[j] << " "<< value[j] << " ";
                }
                sum--;
                j++;
            }
        }
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (m n + n l o g_{2} n)$ ，外部循环遍历R，内部循环遍历I。同时R用sort函数进行排序。
空间复杂度： $O (m + n)$ ，count的长度为n，value的长度为m。

题解 | #数据分类处理#

题目的主要信息：

方法一：

方法二：