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

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

2012-07-04 algo_freek

定义“相等”。同样的顺序？重复的元素？ – SLaks

你的意思是'有没有更好的方法来检查它们是否包含相同的数字？'在我的书籍清单中，平等要求数字都是相同的，并且我认为需要O（n）操作来检查相同的顺序。 –

列表的任何特殊特征？他们排序了吗？数字是否有界？另外，您是否允许使用非恒定数量的额外内存？ – Jon

如果你的意思是，这两个列表包含相同的数字，没有对于排序，你可以使用以下O(n *log n)算法：

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

因此运行上述算法可以在O(n *log n)时间内解决您的问题。

2012-07-04 14:23:50 Sirko

如果数字是整数，则可以使用具有O（n）时间复杂度的桶分类算法（更精确地说，时间复杂度是O（n + r），其中r是数字范围），将问题减少到O （n）+ O（n）+ O（n）= O（n）复杂度 –

或'O（n * log（r））'的二进制基数排序，此时'r'是最大可表示值超过实际存在的最大值。它可以做到位，这很好。 –

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

bool eq = true; 

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

2012-07-04 14:24:04 Ruel

首先检查，如果他们有相同的长度。如果是，你可以把A的数字放在HashSet中。通过B迭代并检查它是否存在于HashSet中。如果它在那里，你可以从HashSet中移除。如果最后HashSet是空的，它们是相等的。这是O（n）

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

2012-07-04 14:24:36 user1168577

谢谢。我也想出了O（n * logn）算法，但我喜欢Urs！ –

谢谢。我也喜欢这个：）。如果你能接受的话，它会有所帮助（再次只在你喜欢它的时候:)）我的回答特别是因为（令人惊讶的）没有人赞成我的:)。 – user1168577

排序2所列出O（nlogn）
然后在他们两人同时去看看它们包含了相同的数字为O（n）

总：O（nlogn）

2012-07-04 14:24:44

回答