algorithm - 检查两个数字列表是否相等

Question

给定两个数字列表 A，B。有没有更好的方法来检查它们是否等于 O(N^2) 解决方案。

Answer 1

对 2 个列表进行排序O(nlogn)
然后同时检查它们并查看它们包含相同的数字O(n)

总计：O(nlogn)

Answer 2

如果您的意思是，两个列表都包含相同的数字而与排序无关，您可以使用以下O( n *log n )算法：

1. 以相同的方式对两个列表进行排序（例如升序）
2. 从顶部开始逐项比较结果列表

步骤（1）需要2 * O( n *log n ) = O( n *log n )时间。第二步以线性O(n)时间运行。

所以运行上面的算法可以及时解决你的问题O( n *log n )。

Answer 3

首先检查它们的长度是否相等。如果是，您可以将 A 的数字放入 HashSet 中。遍历 B 并检查它是否存在于 HashSet 中。如果它在那里，您可以从 HashSet 中删除。如果最后 HashSet 为空，它们是相等的。这是 O(n)

实际上，HashSet 中不允许重复，因此您可以拥有一个 HashMap，其中键作为数字，值作为计数。算法保持不变。每次在 HashMap 递减计数中找到多个 B。如果最后 HashMap 为空，那么它们是相等的。这也是 O(n)。

Answer 4

假设数字在列表中排序，并且两个列表具有相同的长度：

bool eq = true;

for (int i = 0; i < list1.length; i++) {
    if (list1[i] != list2[i]) {
        eq = false;
        last;
    }
}