2

这可能非常微不足道，但我很难找到在不到 n^2 时间内执行的答案。假设我有两个字符串数组，我想知道两个数组中都存在哪些字符串。我将如何在 VB.NET 中有效地做到这一点，或者除了双循环之外还有其他方法吗？

4

4 回答 4

3

简单的方法（假设没有 .NET 3.5）是将一个数组中的字符串转储到哈希表中，然后遍历另一个数组以检查哈希表。这应该比 n^2 搜索快得多。

于 2009-03-23T16:27:54.570 回答
3

如果您对两个数组进行排序，则可以分别遍历它们一次以找到所有匹配的字符串。

伪代码：

while(index1 < list1.Length && index2 < list2.Length)
{
   if(list1[index1] == list2[index2])
   {
      // You've found a match
      index1++;
      index2++;
   } else if(list1[index1] < list2[index2]) {
      index1++;
   } else {
      index2++;
   }
}

然后，您将其减少到进行排序所需的时间。

于 2009-03-23T16:29:52.897 回答
2

对两个列表进行排序。然后您可以确定地知道，如果列表 A 中的下一个条目是“cobble”并且列表 B 中的下一个条目是“确定的”，那么“cobble”不在列表 B 中。只需将指针/计数器推进到列表中的任何一个排名较低的结果并提升排名。

例如：

清单 1：D、B、M、A、I
清单 2：I、A、P、N、D、G

排序：

清单 1：A、B、D、I、M
清单 2：A、D、G、I、N、P

A vs A --> 匹配，存储 A，推进
B vs D --> B D vs D --> 匹配，存储 D，推进
I vs G --> I>G，推进 2
I vs I -->匹配，存储 I，同时推进
M 与 N --> M 列表 1 没有更多项目，退出。
匹配列表是 A,D,I

2 列表排序 O(n log(n))，加上 O(n) 比较使得这个 O(n(log(n) + 1))。

于 2009-03-23T16:29:21.120 回答
2

如果其中一个数组已排序，您可以在内部循环中对其进行二进制搜索，这将减少时间O(n log n)

于 2009-03-23T16:29:44.427 回答