performance - 确定两个列表是否包含相同的数字项而不进行排序

Question

我有两个列表，我需要确定它们是否包含相同的值而不进行排序(即值的顺序无关紧要)。 我知道排序会起作用，但这是性能关键部分的一部分。

项目值在 [-2, 63] 范围内，我们总是比较相同大小的列表，但列表大小范围为 [1, 8]。

示例列表:

A = (0,   0, 4, 23, 10)
B = (23, 10, 0,  4,  0)
C = (0,   0, 4, 27, 10)

A == B is true
A == C is false

我认为一个可能的解决方案是比较两个列表的乘积(将所有值相乘)，但是这个解决方案存在问题。如何处理零和负数。一种解决方法是在乘法之前将每个值加 4。这是我到目前为止的代码。

bool equal(int A[], int B[], int size)
{
    int sumA = 1;
    int sumB = 1;

    for (int i = 0; i < size; i++) {
        sumA *= A[i] + 4;
        sumB *= B[i] + 4;
    }
    return (sumA == sumB)
}

但是，无论列表的顺序/内容是什么，这总是有效吗？换句话说，以下在数学上是正确的吗？所以我真正要问的是以下内容(除非有另一种方法可以解决问题):

给定 2 个相同大小的列表。如果列表的乘积(将所有值相乘)相等，则列表包含相同的值，只要这些值是大于 0 的整数。

Answer 1

假设您提前知道范围，您可以使用计数排序的变体。只需扫描每个数组并跟踪每个整数出现的次数。

Procedure Compare-Lists(A, B, min, max)
  domain := max - min
  Count := new int[domain]
  for i in A:
    Count[i - min] += 1
  for i in B:
    Count[i - min] -= 1
    if Count[i - min] < 0:
      // Something was in B but not A
      return "Different"
  for i in A:
    if Count[i - min] > 0:
      // Something was in A but not B
      return "Different"
  return "Same"

这是线性的 O(len(A) + len(B))