PAT甲级1063 Set Similarity：[C++题解]哈希表、去重

文章目录

• • 题目分析
  • 题目链接

题目分析

来源：acwing

分析：集合相似度是两个集合A、B都有的数字个数，除以两者不同的数字个数，有以下公式:集合相似度 $=\frac{N_c}{N_t}=\frac{A\cap B}{A+B-N_c}$

以样例中的集合1和2为例解释一下：

3 3 99 87 101 4 87 101 5 87 7 99 101 18 5 135 18 99 2 1 2 1 3

样例1：两个集合中元素个数分别为：A = 3个，B = 3个(注意不是4个，需要去重)，两个集合相同元素2个，所以$N_c=2$,$N_t=3+3-2=4$,这样计算出来的50%。

求两个集合的交集：Nc //时间复杂度O(M) for(auto x: A)if(x in B)Nc ++;

ac代码

#include<bits/stdc++.h> using namespace std; const int N =55; unordered_set<int> S[N]; //有几个集合就开几个hash表,并且是set去重int main(){int n, k;cin >> n;for( int i = 1; i<= n; i++){int m;scanf("%d",&m);while(m--){int x;scanf("%d",&x);S[i].insert(x); //插入到集合i的hash表中}}//询问cin >> k;while(k--){int a, b;scanf("%d%d",&a,&b);int nc = 0; //分子//遍历集合a中的每个元素，如果在集合b中出现过，就统计下//这样nc就是公共元素的个数，这里如果是公共元素，则.count(x)==1for( auto x: S[a]) nc += S[b].count(x);//分母int nt =S[a].size() + S[b].size() - nc;//%在C语言输出，需要转义 ，写成%% printf("%.1lf%%\n", (double)nc/nt * 100);}}

题目链接

PAT甲级1063 Set Similarity
https://www.acwing.com/problem/content/1551/

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的PAT甲级1063 Set Similarity：[C++题解]哈希表、去重的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。