如何提高效率

Question

我有以下作业问题:假设你有两个n个元素的序列S1和S2，可能包含重复的，在它们上定义了一个总的顺序关系。描述一种有效的算法来确定S1和S2是否包含相同的元素集。分析了该方法的运行时间

为了解决这个问题，我使用retainAll和HashSet比较了两个数组的元素。

Set1.retainAll(new HashSet<Integer>(Set2));

这将在恒定的时间内解决问题。为了提高效率，是否需要在retainAll步骤之前对两个数组进行排序？

Answer 1

从您发布的代码中，我怀疑您错过了任务的要点。这个想法不是使用Java库来检查两个集合是否相等(因此，您可以使用collection1.equals(collections2)。更确切地说，重点是提出一个比较集合的算法。Java API没有指定算法:它隐藏在实现中。

在不提供答案的情况下，让我给你一个算法的例子，它可以工作，但不一定有效：

for each element in coll1
    if element not in coll2
        return false
    remove element from coll2
return coll2 is empty

问题指定序列是有序的(即定义了总顺序关系)，这意味着您可以比上面的算法做得更好。

通常，如果要求您演示一个算法，最好使用本机数据类型和数组-否则，库类的实现可能会显着影响效率，并隐藏您希望在算法本身上收集的数据。