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

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))