VB.NET 数组交集
这可能非常微不足道，但我很难找到在不到 n^2 时间内执行的答案。 假设我有两个字符串数组，我想知道两个数组中都存在哪些字符串。 在 VB.NET 中我该如何有效地做到这一点，或者除了双循环之外还有其他方法可以做到这一点吗？
This could be terribly trivial, but I'm having trouble finding an answer that executes in less than n^2 time. Let's say I have two string arrays and I want to know which strings exist in both arrays. How would I do that, efficiently, in VB.NET or is there a way to do this other than a double loop?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
一种简单的方法（假设没有 .NET 3.5）是将字符串从一个数组转储到哈希表中，然后循环遍历另一个数组，对照哈希表进行检查。 这应该比 n^2 搜索快得多。
The simple way (assuming no .NET 3.5) is to dump the strings from one array in a hashtable, and then loop through the other array checking against the hashtable. That should be much faster than an n^2 search.
如果对两个数组进行排序，则可以分别遍历它们一次以查找所有匹配的字符串。
伪代码：
那么您就将其减少到进行排序所需的时间。
If you sort both arrays, you can then walk through them each once to find all the matching strings.
Pseudo-code:
Then you've reduced it to the time it takes to do the sorting.
如果其中一个数组已排序，您可以在内部循环中对其进行二分搜索，这会将时间减少到
O(n log n)If one of the arrays is sorted you can do a binary search on it in the inner loop, this will decrease the time to
O(n log n)对两个列表进行排序。 然后，您可以确定地知道，如果列表 A 中的下一个条目是“cobble”，而列表 B 中的下一个条目是“definite”，则“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 与 A --> 匹配、存储 A、同时推进
B vs D --> 乙
D vs D --> 匹配、存储 D、同时推进
I vs G --> I>G，前进 2
我对我——> 匹配、存储 I、推进两者
M vs N --> 中号
列表 1 没有更多项目，退出。
匹配列表是 A,D,I
2 个列表排序 O(n log(n))，加上 O(n) 比较使得这个 O(n(log(n) + 1))。
Sort both lists. Then you can know with certainty that if the next entry in list A is 'cobble' and the next entry in list B is 'definite', then 'cobble' is not in list B. Simply advance the pointer/counter on whichever list has the lower ranked result and ascend the rankings.
For example:
List 1: D,B,M,A,I
List 2: I,A,P,N,D,G
sorted:
List 1: A,B,D,I,M
List 2: A,D,G,I,N,P
A vs A --> match, store A, advance both
B vs D --> B
D vs D --> match, store D, advance both
I vs G --> I>G, advance 2
I vs I --> match, store I, advance both
M vs N --> M
List 1 has no more items, quit.
List of matches is A,D,I
2 list sorts O(n log(n)), plus O(n) comparisons makes this O(n(log(n) + 1)).