algorithm - 如何使用最坏情况 O(n^2) 来搜索 2 个列表并将公共(public)值添加到第 3 个列表？

Question

我需要帮助为一个算法制作一个伪代码，该算法采用两个整数列表，并创建一个由出现在两个列表中的那些整数组成的列表(最终列表中的每个整数应该只出现一次)。该算法需要实现比 Θ(n²) 渐近更好的最坏情况性能，其中 n 是两个输入列表的长度之和。

这是我目前的情况，但我对此没有信心:

• 从两个列表 a 和 b 开始。结果列表将是 c。
• 使用合并排序算法对列表 b 进行排序。
• 从索引 i=0 开始，遍历列表 a。
• 使用二进制搜索算法在列表 b 中搜索 a[i] 的值
• 如果 a[i] 在 b 中找到，而 a[i] 不在 c 中.. 将 a[i] 附加到 c。

Answer 1

1. 对两个列表进行排序。此步骤的复杂度顺序为 n log n。使用 quick sort .
2. 比较排序列表并找到共同元素。这一步的复杂度阶数是n。

int i = 0, j = 0;
while ((j < b.size()) && (i < a.size()))
{
   if (a[i] < b[j])
   {
       i++;
       continue;
   }
   if (a[i] > b[j])
   {
       j++;
       continue;
   }
   // if we are here, a[i] == b[j]
   c.push_back(a[i]);
   i++;
   j++;
   // skip identical elements
   while ((i < a.size()) && (a[i-1]==a[i]))
   {
       i++;
   }
   while ((j < b.size()) && (b[j-1]==b[j]))
   {
       j++;
   }
}
return c;

总复杂度阶数是n log n。