delphi - 如何在delphi中比较两个数组并从中删除重复项

Question

我有两个数组。Array1 持有医学术语，而 array2 持有简单的英语术语。医学术语数组中包含一些非医学英语单词（在 array1 中重复）。这些是 array1 中的 20,000 个和 array2 中的超过 15000 个。使用delphi比较两个数组并从array1中删除重复单词的最快方法是什么？

Answer 1

如果您的数组已排序，请保留两个指针p1- 和p2toarray1和array2resply。将它们初始化为指向array1and的第一个元素array2。

对于array1从第一个开始的每个条目，查看它是否是单词array2[p2]。如果是，只需将其从array1. 如果不是，则递增p2直到

( (array1[p1] >= array2[p2]) and (array1[p1] < array2[p2+1]) ),  

array1[p1]如果你找到一个命中删除。

需要O(n)时间。有O(nlogn)时间排序算法。

Answer 2

如果数组未排序，则此方法更快： 1. 将 array2 中的所有单词填充到字典中。2. 遍历array1，查找字典中的每个单词，如果找到就删除它。

第 1 步和第 2 步都需要 O(n) 时间。

如果你有一个旧版本的 delphi，你必须使用一个字典类，比如在你的 delphi 安装的 Memini.Pas 文件中的 THashedStringList。对于非常大的 N，它会退化，但对于 20.000 个条目，它仍然非常快。

可以在此处找到能够在 O(1) 中存储和查找 1 亿个字符串的非常快速的实现。这篇文章是德文的，但代码是英文的并且可以理解。