V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
naoh1000
V2EX  ›  算法

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

  •  
  •   naoh1000 · 2021-02-02 12:02:43 +08:00 via iPhone · 1412 次点击
    这是一个创建于 1151 天前的主题,其中的信息可能已经有所发展或是发生改变。
    前端程序员,刚才听到 HR 说来面试的求交集只会两个 for,我想了一下也确实只想到一个 for 把集合 A 加入 hashmap,另一个逐项查找集合 B 是否在 hashmap 中,还有更好的方法吗?
    4 条回复    2021-02-02 12:51:12 +08:00
    elonmask
        1
    elonmask  
       2021-02-02 12:17:55 +08:00
    很明显得用 set,数据是整数同时值比较小的话,可以数组,类似那种计数的方式
    pianjiao
        2
    pianjiao  
       2021-02-02 12:32:41 +08:00 via Android
    map set
    mcfog
        3
    mcfog  
       2021-02-02 12:39:14 +08:00 via Android
    搞清楚 M+N 复杂和 M*N 复杂就行了,很容易证明理论最小复杂度就是 M+N
    Inf1nity
        4
    Inf1nity  
       2021-02-02 12:51:12 +08:00
    我觉得无论如何都要遍历两次,复杂度 O(M+N)。各类 Set 应该就可以满足需要了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4509 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 05:34 · PVG 13:34 · LAX 22:34 · JFK 01:34
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.