集合求交集有比两个 for 效率更高的方法吗？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1397 天前的主题，其中的信息可能已经有所发展或是发生改变。

前端程序员，刚才听到 HR 说来面试的求交集只会两个 for，我想了一下也确实只想到一个 for 把集合 A 加入 hashmap，另一个逐项查找集合 B 是否在 hashmap 中，还有更好的方法吗？

4 条回复 • 2021-02-02 12:51:12 +08:00

elonmask

2021-02-02 12:17:55 +08:00

很明显得用 set，数据是整数同时值比较小的话，可以数组，类似那种计数的方式

pianjiao

2021-02-02 12:32:41 +08:00 via Android

map set

mcfog

2021-02-02 12:39:14 +08:00 via Android

搞清楚 M+N 复杂和 M*N 复杂就行了，很容易证明理论最小复杂度就是 M+N

Inf1nity

2021-02-02 12:51:12 +08:00

我觉得无论如何都要遍历两次，复杂度 O(M+N)。各类 Set 应该就可以满足需要了。