时间戳

首页 > 解决方案 > 用字典优化O(n^2)算法，有没有可能走得更远

algorithm - 用字典优化O(n^2)算法，有没有可能走得更远

问题描述

有2套：

Set 1 of values（包含所有可能的值） Set 2 of values（包含 Set 1 中的一些可能值）

对于每场比赛，我们将在第 1 组中指出我们找到了它。

O(n^2) 的排序方式是：

foreach(var set1Variable in set1) {
    foreach(var set2Variable in set2) {
        if(set1Variable == set2Variable )
            set1.indexOf(set1Variable).Found = true;
    }
}

它可以用字典进行优化。

第一个解决方案是“好”或“坏”。字典呢？我们应该考虑什么？解决这个问题的最佳方法是什么，为什么？

标签： algorithmlanguage-agnostic

解决方案

您可以创建一个 TreeSet 并将所有集合添加到其中。

TreeSet myTreeSet = new TreeSet();
myTreeSet.addAll(myHashSet);
System.out.println(myTreeSet);

假设您的集合大小为 n，空间复杂度为 O(n)，时间复杂度为 O(nlogn)

推荐阅读