java - 如何提高效率

Question

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

为了解决这个问题，我使用 keepAll 和 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

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

一般来说，如果要求您演示算法，最好坚持使用 native 数据类型和数组 - 否则库类的实现会显着影响效率并隐藏您想要在算法本身上收集的数据。