查找两个数组之间匹配项的最快方法是什么？

Question

目前，我正在将每个整数元素彼此进行测试，以找出哪些相匹配。数组不包含其自身集合中的重复项。此外，这些数组的长度并不总是相等的。有没有什么技巧可以加快速度？我需要执行这个操作数千次，所以它开始成为我的程序的瓶颈，该程序是使用C#编写的。

- John Sheares

---

你是想要一个两个数组中都存在的整数的唯一列表吗？ - Thomas

补充一下Thomas的评论，这些数组是有序的吗？ - Robert Jeppesen

这是另一种表达方式。两个集合中共同的唯一列表。是的，它们是有序的。 - John Sheares

我们能够利用的项目数量或整数范围是否有任何限制？ - Mark Byers

Answer 1

您可以使用LINQ：

var query = firstArray.Intersect(secondArray);

如果数组已经排序，您可以自己遍历这两个数组：

int[] a = { 1, 3, 5 };
int[] b = { 2, 3, 4, 5 };

List<int> result = new List<int>();
int ia = 0;
int ib = 0;
while (ia < a.Length && ib < b.Length)
{
    if (a[ia] == b[ib])
    {
        result.Add(a[ia]);
        ib++;
        ia++;
    }
    else if (a[ia] < b[ib])
    {
        ia++;
    }
    else
    {
        ib++;
    }
}

- Mark Byers

---

@Mark：你的代码默默地假设数组已经排序。 - Vlad

约翰已经在上面的评论中说明了数组是有序的。 - Robert Jeppesen

Answer 2

使用 HashSet

var set = new HashSet<int>(firstArray);
set.IntersectWith(secondArray);

该集合现在仅包含两个数组中都存在的值。

- Josh

---

我认为你想要使用.Intersect而不是.Union。 - Ian Mercer

刚刚尝试了使用IntersectWith的HashSet，与遍历所有元素相比，速度慢了一倍。 - John Sheares

Answer 3

如果这样的比较成为您程序的瓶颈，那么您可能正在使用不合适的数据结构。最简单的方法可能是保持数据排序。然后，要查找共同条目，您只需要遍历两个数组一次。另一个选择是将数据保存在 HashSet 中。

- Vlad