关于算法-数据结构:PAT甲级1063-Set-Similarity

题目粗心：

给定N个汇合,要求计算查问的2个汇合的Nc/Nt的值,其中Nc指的是2汇合雷同元素的个数,Nt指的是2汇合不同元素的个数.

算法思路:

很天然就想到用set容器来保留数据元素了,最显著的特色就distinct，要求元素不反复的个数,咱们首先应用unordered_set<int> sets[55]保留每个容器的所有元素(主动去反复了)，而后编写函数caculate用来计算2个汇合的并集和交加元素个数,就是遍历其中一个汇合而后在另外一个汇合应用find函数判断是否查找胜利,如果是就累计Nc，否则就累计Nt(初始为其中一个汇合的元素个数),最初计算比率输入即可

留神点：

1、如果通过将2汇合增加进另外一个新的汇合中计算不同元素的大小,最初一个点会超时。
2、%要写成%%输入
3、这里只须要set的去重操作，所以应用unordered_set比拟节省时间
4、不要应用algorithm自带的set_intersection和set_union办法，无奈通过测试。

提交后果：

AC代码：

#include <cstdio>
#include <unordered_set>


using namespace std;

unordered_set<int> sets[55];//N个汇合

void caculate(int first,int second){
    int Nt = sets[first].size();// first汇合和second汇合的并集元素总个数
    int Nc = 0;// first汇合和second汇合的交加元素总个数
    unordered_set<int>::iterator it;
    for(it=sets[second].begin();it!=sets[second].end();++it){
        if(sets[first].find(*it)!=sets[first].end()){
            // 在first汇合中找到second汇合中的元素
            ++Nc;
        } else {
            // 没有找到
            ++Nt;
        }
    }
    printf("%.1f%%\n",Nc*100.0/Nt);
}

int main(){
    int N;//汇合数目
    scanf("%d",&N);
    int M;// 每一个汇合的元素个数
    int num;// 汇合元素
    for (int i = 1; i <= N; ++i) {
        scanf("%d",&M);
        for (int j = 0; j < M; ++j) {
            scanf("%d",&num);
            sets[i].insert(num);
        }
    }
    int K;//查问个数
    scanf("%d",&K);
    int index_first,index_second;// 查问的第一个汇合和第二个汇合的下标
    for (int k = 0; k < K; ++k) {
        scanf("%d %d",&index_first,&index_second);
        caculate(index_first,index_second);
    }
    return 0;
}