java - 如何避免时间复杂度 O(n^2)？

Question

我有以下这段代码：

for(ArticleBasketInBean basketBean : bean.getBasket()) {
    for(ArticleDTO article : dto.getArticleList()) {
        if(basketBean.getArticleReference().equals(article.getArticleReference())) {
            article.setAddedToBasket(true);
        }
    }
}

显然上述操作的时间复杂度是 O(n^2)。对于这种情况articleReference是独一无二的。所以返回的列表bean.getBasket()没有重复articleReference，返回的列表也是如此dto.getArticleList()。

我想避免这种嵌套迭代并想编写更快的代码。我怎样才能做到这一点？

Answer 1

用于java.util.HashSet缓存一组引用，当然，假设这些集不是太大。有了一个好的散列函数，这应该会让你回到 O(n)。

Answer 2

一个简单的break将拯救你。

    for(ArticleBasketInBean basketBean : bean.getBasket()) {
    for(ArticleDTO article : dto.getArticleList()) {
        if(basketBean.getArticleReference().
                                  equals(article.getArticleReference())) {
            article.setAddedToBasket(true);
            break;
        }
    }
}

Answer 3

如果您没有太多文章/篮子，并且正如您所说的参考文献是独一无二的，您可以这样做；让我们称R参考A的类型、文章B的类型、篮子的类型：

// since all references are unique we can use that, but see below
Map<R, A> mappedArticles = new IdentityHashMap<>();

// inject articles based on references in the map, then

A article;

for (B basket: bean.getBasket())
    article = mappedArticles.get(basket.getArticleReferences());
    if (article != null)
        article.setAddedToBasket(true);

// Full list of articles is in the map's .values()

笔记：

• 注意身份哈希集的使用；您可能想要为引用实现 equals/hashcode（或者您使用的类型可能已经为您实现了它们）；
• 您的地图可能会被“流过”的文章填充，在这种情况下，您只能创建一次（如果是，请使其线程安全！）。