PAT 解题报告 1063. Set Similarity (25)

题目描述:

Given two sets of integers, the similarity of the sets is defined to be Nc/Nt*100%, where Nc is the number of distinct common numbers shared by the two sets, and Nt is the total number of distinct numbers in the two sets. Your job is to calculate the similarity of any given pair of sets.

求两个set的similarity

算法分析:

想 了一会也没有太好的很精妙的算法, 于是直接模拟题目做. 最好利用ordered set每个set都排序好, 那么求任意两个set的交集和并集都是线性的O(M). 因为大概有O(N^2)个query 那么总的时间是O(N^2 M), 时间复杂度上刚刚好差不多可以过OJ. 我直接模拟写的, 一次过>_<.

注意点:

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on September 2, 2013