algorithm - 检查 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 ，那么我们可以说这两个数组是相似的。有人可以提供一个测试用例，在该用例中它不起作用(但我希望它应该起作用!)？

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

Answer 1

你可以在 O(max(L_A, L_B)) time 内完成，其中 L_A 和 L_B 分别是 A 和 B 的长度，但代价是使用 O(M) space，其中 M 是数组(即有这样的常量 min 和 max ，因此 min <= a, b <= max 对 A 中的每个 a 和 B 中的每个 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"

如果数组非常大，但它们的所有值都在一个小范围内，这种方法很实用。