V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
yodhcn
V2EX  ›  JavaScript

在对一个较长的数组去重,同时要求返回重复元素索引时,哪种算法最快?

  •  
  •   yodhcn · 2021-01-02 12:33:51 +08:00 · 2756 次点击
    这是一个创建于 1412 天前的主题,其中的信息可能已经有所发展或是发生改变。
    9 条回复    2021-01-03 10:08:12 +08:00
    Inf1nity
        1
    Inf1nity  
       2021-01-02 12:37:47 +08:00   ❤️ 1
    我只能想到用扫描数组,用哈希表存 <数,索引 list> 这个键值对,然后再扫一遍根据哈希表的 key 重建数组,重复元素索引这个时候也可以得到。
    shiji
        2
    shiji  
       2021-01-02 12:42:15 +08:00 via iPhone   ❤️ 1
    能想到的是 O(n)
    HashMap
    键是 数组得每个值
    值是 List<Integer> 存的是遇到重复的索引
    shiji
        3
    shiji  
       2021-01-02 12:43:06 +08:00 via iPhone
    尴尬了,手机打字慢 ,和楼上说的一样
    Jooooooooo
        4
    Jooooooooo  
       2021-01-02 13:28:45 +08:00   ❤️ 1
    你要快就用空间换时间

    弄个 map 出来
    Lemeng
        5
    Lemeng  
       2021-01-02 14:40:29 +08:00
    楼顶的大佬说的不错
    hello2060
        6
    hello2060  
       2021-01-02 18:30:10 +08:00
    数组中每个元素读一遍 O(n)
    找重用哈希每个元素 O(1) 全数组就是 O(n)
    输出也是 O(n)
    所以最后就是 O(n)
    laminux29
        7
    laminux29  
       2021-01-02 19:12:17 +08:00   ❤️ 1
    关键在于 [较长] ,到底有多长,以及需要达到怎样的性能。这些参数不同,做法完全不一样。

    比如,千万级别,性能 10 秒内,那么直接 for 循环,现在最新的 CPU 完全能扛得住。

    数据量更大一些,同时需要考虑性能,此时按照楼上老哥们的方法,开始使用 map 等类似的数据结构,用空间换时间。

    数据量再大一些,大到谷歌或百度这种级别,搜索引擎对 URL 进行唯一性判定的需求,那做法又完全变了,需要采用集群 + 分布式 hash 映射 + 允许一定量的重复计算并使用最终一致性。原理看似一句话,但下面设计到的成本控制、智慧运维、数据中间建设、通信问题等等,整个工程设计起来就相当复杂了。
    stevefan1999
        8
    stevefan1999  
       2021-01-02 20:30:49 +08:00
    hash tree, i.e. merkele tree, 也就是 bitcoin 用的那個
    xuanbg
        9
    xuanbg  
       2021-01-03 10:08:12 +08:00   ❤️ 1
    再怎么长,也得遍历。所以时间复杂度最小也得 O(n)。你要是来个循环嵌套,那就是 O(n^2)。如果机灵一点把每个元素 hash 一下存到 hashmap 做 key,那么就不用嵌套循环了,每次都去 hashmap 里面找一下 key 存不存在,不存在就把自己存进去,存在就在另一个重复元素集合里面把自己的索引存进去。最后输出重复元素集合就行了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2574 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 16:02 · PVG 00:02 · LAX 08:02 · JFK 11:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.