如何在两个列表中找到共同的元素?在时间复杂性和空间复杂性方面的最佳解决方案

Question

我有两个列表，每个列表中的元素都是一个employee对象。每个员工都有一个id（int）和name（string）。

这两份名单可能都有一些普通员工，这些员工需要获得一些特殊特权。任务是找到那些常见的。

一种解决方案可以是使用嵌套循环，但这将是O（n^2）。另一种方法是根据员工id对它们进行排序，这将是O（nlogn），然后使用类似于合并的逻辑。我们同时遍历它们，当我们发现具有相同id的员工时，我们会捕获它。解决它的最佳方法是什么？

Answer 1

听起来你想要得到两个链表的交集。为此，您必须首先将它们排序为O（nlogn），n是最大的一个的大小。然后，您构建一个包含常见元素的列表：从列表的开头开始，并根据员工ID推进指针。

if (list1.ID == list2.ID)
{
  copyToNewList(list1.ID);
}
else
if(list1.ID > list2.ID)
{
   lsit2 = list2->next;
}
else
{
  lsit1 = list1->next;
}

当你浏览完其中一个列表，而另一个仍然有元素时，你必须考虑这个情况——但你已经明白了。

如果空间不是你关心的问题，而你只关心速度，你可以在任何列表中分配一个最大ID大小的数组。在这个数组中，每个索引都将代表ID。现在，您可以扫描第一个数组并查找每个元素array[ID] = 1。然后扫描第二个列表并：

if（array[ID]==1）array[ID]=3；其他的array[ID]=2；现在，您的数组可以告诉您哪些元素是常见的，哪些仅在列表1中，哪些仅位于列表2中——如果您需要这些信息——在O（max（m，n））中；

请注意，此解决方案对于数量有限的ID是有效的-如果您希望ID数量在数万或数十万左右，则不仅空间效率低，而且从阵列中检索数据也需要很长时间。

编辑：事实上，如果你使用哈希表而不是数组，你会得到一个更节省空间的解决方案，它仍然是O（max（m，n））