检查2数组是没有散列或排序相似 [英] Check if 2 arrays are similar without hashing or sorting

问题描述

我们需要检查，如果2个数组是相似与否。该元素可以是重复的为好。 例如A = {2,3,4,5,6,6}和B = {3,6,2,4,6,5}是相似的。

We need to check if 2 arrays are similar or not. The elements can be duplicate as well. For example A = {2,3,4,5,6,6} and B = {3,6,2,4,6,5} are similar.

我有一个天真的解决方案：

I have a naive solution :

foreach i:int in arr1
 foreach j:int in arr2
  {
    if(i == j)
     j = -1;
  } 

现在，如果j的所有元素都是-1，那么我们可以说，2阵列是相似的。有人可以给一个测试案例中，这是不行的（我希望它应该工作，但！）？

Now if all the elements of j are -1 , then we can say that the 2 arrays are similar. Can someone give a test case in which this won't work (i hope it should work though!) ?

另外这是O（n ^ 2）。我们可以做的更好？排序和散列都是不允许的。

Also this is O(n^2). Can we do better ? Sorting and Hashing are not allowed.

推荐答案

您可以使用您从其中一人构建一个二叉搜索树。 现在去了另外一个，并检查值已经在二叉搜索树。 在O（nlgn），并使用O该持斧（n）的空间。

You can use a binary search tree that you build from one of them. Now go over the other one and check if the value is already in the binary search tree. This one runs in O(nlgn) and use O(n) space.

这篇关于检查2数组是没有散列或排序相似的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！