c - 以最有效的方式比较两个字符串数组

Question

这个问题是关于在主数组中搜索一个字符串（包含所有 UID 的列表）。第二个数组包含所有要搜索的字符串。

例如：

第一个数组（主列表）包含： UID1 UID2 UID3... UID99

第二个数组包含：UID3 UID144 UID50

如果在第一个数组中找到匹配项，则返回 1，否则返回 0。所以上面例子的输出应该是101.

解决上述问题的最有效方法（针对 C）可能是什么，请记住，处理此问题的传统方法是n^2！！！

score 1 · Accepted Answer

1

对主字符串数组进行排序并进行二进制搜索。

于 2013-11-01T10:08:19.643 回答

score 0 · Accepted Answer

高效在什么方面？

我会接受@Trying 的建议，作为在良好的运行速度、低内存使用和非常（非常！）低实现复杂性之间的一个很好的折衷。

只需使用qsort()对第一个主数组进行排序，然后使用bsearch()搜索它。

假设主数组中有n 个元素，第二个数组中有m个元素，这应该给出 O( m *log n ) 时间复杂度，这看起来不错。

score 0 · Accepted Answer

这个问题主要有两种好的方法：

使用二分搜索：二分搜索需要对第一个数组中的 UID 进行排序，并允许您在O(log n)其中找到n主数组中元素数的解决方案。总的复杂性将O(m log n)与m要搜索的元素的数量有关。
使用hashmap：您可以将主数组的元素存储在 hashmap ( O(n)) 中，然后检查第二个数组的元素是否在 hashmap ( O(m)) 中。总复杂度为O(n+m).

虽然第二种方法的复杂性看起来更好，但您必须记住，如果您的哈希不好，它可能是O(m*n)最坏的情况（但您不太可能）。此外，您将使用更多内存并且操作也更慢。在你的情况下，我会使用第一种方法。

score 0 · Accepted Answer

另一种选择是为 Master 列表中的字符串构建一个哈希，它是单个 O(M)（假设长度为 O(1)），然后假设哈希均匀分布，搜索单个元素平均需要 O (M/S)，其中 S 是散列的大小（均匀分布意味着平均而言这是映射到同一散列条目的元素数量）。您可以进一步控制大小以微调空间和效率之间的权衡

4 回答 4