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)。