问技能集匹配算法

EN

取决于技能的数量。如果它是小的，我会用素数。更精确地说:创建表skills[n] (其中n是用户数)。然后，如果用户知道第一个技能(在这种情况下是C)乘以第一个素数(2)，如果他知道第二个技能乘以第二个素数，等等。

然后，如果您想要查找用户i是否知道第二个技能(C++)，只需检查skills[i]%3==0

例如:寻找技能值:用户1知道技能1 (C)和技能3 (Perl)，这意味着他的技能值是1*2*5=10，用户2知道技能3，所以他的技能值是1*5。

查找所有可以使用C、C++、Perl匹配2的用户：

for(int i=0;i<n;i++){
    int howMany=0;
    if(skill[i]%2)==0)
        howMany++;
    if(skill[i]%5)==0)
        howMany++;
    if(skill[i]%7)==0)
        howMany++;
    if(howMany>=2)
        addToResult(i);
 }

或者，您可以创建一个2d数组，其中列对应于person，行对应于技能。如果值设置为1，则表示person知道如何使用该技能，如果设置为0，则不使用。然后，只需添加所有需要的行的值，就可以找到合适的用户。

示例：

 C    1 | 0 | 0 |
 C++  0 | 0 | 1 |
 PERL 1 | 1 | 1 |

让我们找一个知道C，Perl的人--如果我们从第1行和第3行中添加所有值，我们就会得到

 SUM  2 | 1 | 1 | 

只有列1有值>=2，这意味着它是满足条件的唯一一列。现在，让我们尝试找到使用C、C++和PERL的人，匹配2

SUM  2 | 1 | 2

我们现在知道用户1和用户3的值为sum >=2，因此它们满足了这些条件。

以下是有效的算法:-

1. 对每个技能使用id's的HashSet
2. 要检查id是否有技能，只需签入HashSet即可

注：

该算法是O(n*S)算法，其中n为人数，S为所需技能数。我认为没有更快的算法。

编辑：

与其搜索所有的n个人，你还可以只与那些在所需的集合中至少具备一种技能的人进行检查。在许多情况下，这将节省大量的计算时间。