算法:选择集合的公共(public)元素

Question

我最近不得不编写以下算法:

Given a group of tags, and a group of blog posts, where a blog post may contain zero-to-many tags, return the tags common to all posts.

这种比较是在内存中进行的 - 访问任一集合不会导致跨网络旅行(即，到数据库等)。

此外，Tags 集合没有对包含它的 BlogPosts 的引用。 BlogPosts 包含一组 Tags。

下面是我的实现。它表现得很好，但我很好奇是否有更好的方法来实现它。

我的实现是在 Actionscript 中，但我对算法的角度更感兴趣，所以任何语言的示例都可以。 (但如果我不懂语言，我可能会要求你澄清一些方面)

任何改进的例子都会受到极大的欢迎。

    private function getCommonTags(blogPosts:Vector.<BlogPost>):Vector.<Tag>
    {
        var commonTags:Vector.<Tag> = new Vector.<Tag>();
        if (!blogPosts || blogPosts.length == 0)
            return commonTags;

        var blogPost:BlogPost = blogPosts[0];
        if (!blogPost.tags || blogPost.tags.length == 0)
            return commonTags;

        commonTags = Vector.<Tag>(blogPosts[0].tags);

        for each (var blogPost:BlogPost in blogPosts)
        {
            if (!blogPost.tags || blogPost.tags.length == 0 || commonTags.length == 0)
                // Updated to fix bug mentioned below
                // Optomized exit - there are no common tags
                return new Vector.<Tag>();

            for each (var tag:Tag in commonTags)
            {
                if (!blogPost.containsTagId(tag.id))
                {
                    commonTags.splice(commonTags.indexOf(tag),1);
                }
            }
        }
        return commonTags;
    }

Answer 1

好吧，您只需要一个计算两个集合的交集的高效算法，因为您可以为两个以上的集合重复调用该算法。

一种快速算法是将第一个集合的项目添加到哈希表中，然后遍历第二个集合检查哈希表是否存在；如果是，则将其添加到要在交集中返回的项目列表中。