用字典优化O(n^2)算法，是否可以更进一步

Question

有2组：

设置 1 个值（包含所有可能的值）第 2 组值（包含第 1 组中的一些可能值）

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

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

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

可以用字典优化。

如何'good'或'bad'是第一种解决方法。字典呢？我们应该考虑什么？对此进行排序的最佳方法是什么？为什么？

Answer 1

建议的解决方案是 O(n^2) 时间，没有额外的 space。
一个字典解决方案（其中最小集合的所有元素都是放入字典）可以是 O(n) / O(nlogn) （取决于 which dictionary, tree based or hash) time and O(n) space.
你也可以获得 O(nlogn) 的时间，不需要额外的 space，通过排序两个容器，然后并行迭代以找到匹配项目。

哪个更好？

取决于具体的需求和限制。如果你负担不起额外的 space，字典解决方案变得 none 可行。如果 O(nlogn) 时间太多，你应该坚持哈希。

附录：方案3（排序）伪代码：

sort(set1)
sort(set2)

iter1 = set1.iterator()
iter2 = set2.iterator()
while iter1.has_next() and iter2.has_next():
  if iter1.item() == iter2.item():
    set2.add(iter1.item())
    iter1.next()
    iter2.next()
  else if iter1.item() < iter2.item():
    iter1.next()
  else:
    iter2.next()

Answer 2

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

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

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

用字典优化O(n^2)算法，是否可以更进一步

Optimizing the O(n^2) algorithm with dictionary, is it possible to go further

language-agnostic

algorithm