检查2个阵列是否相似而不进行散列或排序

Question

我们需要检查2个阵列是否相似.元素也可以是重复的.例如,A = {2,3,4,5,6,6}和B = {3,6,2,4,6,5}是相似的.

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

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

现在,如果j的所有元素都是-1,那么我们可以说2个数组是相似的.有人可以提供一个不起作用的测试用例(我希望它应该工作!)？

这也是O(n ^ 2).我们可以做得更好吗？不允许排序和散列.

Answer 1

你可以在O(max(L _A,L _B))时间内完成它,其中L _A和L _B分别是A和B的长度,但是以使用O(M)空间的价格,其中M是允许的范围在阵列中的值(即,有这样的常量min和max,以便min <= a, b <= max为所述的每一个和b在乙成立).

seen = array[min..max]
foreach a in A
    seen[a] = 'a'

foreach b in B
    if seen[b] != 'a'
        // A didn't contain b
        return "A and B are not equivalent"
    else
       seen[b] = 'a,b'

foreach s in seen
    if s == 'a'
        // A did contain a which was not in B
        return "A and B are not equivalent"

return "A and B are equivalent"

如果阵列非常大,这种方法是实用的,但它们的所有值都适合小范围.

Answer 2

您可以使用从其中之一构建的二叉搜索树。现在检查另一个并检查该值是否已经在二叉搜索树中。这个运行时间复杂度为 O(nlgn) 并使用 O(n) 空间。