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

[yodhcn]

[Inf1nity]

我只能想到用扫描数组，用哈希表存 <数,索引 list> 这个键值对，然后再扫一遍根据哈希表的 key 重建数组，重复元素索引这个时候也可以得到。

[shiji]

能想到的是 O(n)
HashMap
键是 数组得每个值
值是 List<Integer> 存的是遇到重复的索引

[shiji]

尴尬了，手机打字慢 ，和楼上说的一样

[Jooooooooo]

你要快就用空间换时间

弄个 map 出来

[Lemeng]

楼顶的大佬说的不错

[hello2060]

数组中每个元素读一遍 O(n)
找重用哈希每个元素 O(1) 全数组就是 O(n)
输出也是 O(n)
所以最后就是 O(n)

[laminux29]

关键在于 [较长] ，到底有多长，以及需要达到怎样的性能。这些参数不同，做法完全不一样。

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

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

数据量再大一些，大到谷歌或百度这种级别，搜索引擎对 URL 进行唯一性判定的需求，那做法又完全变了，需要采用集群 + 分布式 hash 映射 + 允许一定量的重复计算并使用最终一致性。原理看似一句话，但下面设计到的成本控制、智慧运维、数据中间建设、通信问题等等，整个工程设计起来就相当复杂了。

[stevefan1999]

hash tree, i.e. merkele tree, 也就是 bitcoin 用的那個

[xuanbg]

再怎么长，也得遍历。所以时间复杂度最小也得 O(n)。你要是来个循环嵌套，那就是 O(n^2)。如果机灵一点把每个元素 hash 一下存到 hashmap 做 key，那么就不用嵌套循环了，每次都去 hashmap 里面找一下 key 存不存在，不存在就把自己存进去，存在就在另一个重复元素集合里面把自己的索引存进去。最后输出重复元素集合就行了。