确定两个列表是否包含相同的数字项而不进行排序 [英] Determing if two lists contain the same numeric items without sorting

问题描述

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

I have two lists and I need to determine if they contain the same values without sorting (ie. order of values is irrelevant). I know sorting the would work, but this is part of a performance critical section.

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

Item values fall within the range [-2, 63] and we're always comparing equal size lists, but the list sizes range from [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.这是我到目前为止的代码.

---

I think a possible solution would be to compare the product of the two lists (multiply all values together), but there are problems with this solution. What to do with zero and negative numbers. A workaround would be adding 4 to every value before multiplying. Here's the code I have so far.

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

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

But, would this always work no matter what the order/contents of the list were? In other words is the following mathematically true? So what I'm really asking is the following (unless there's another way to solve the problem):

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

推荐答案

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

Assuming you know the range ahead of time, you can use a variation on counting sort. Just scan through each array and keep track of how many times each integer occurs.

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

这篇关于确定两个列表是否包含相同的数字项而不进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！