推荐关注
› Meteor
› JSLint - a JavaScript code quality tool
› jsFiddle
› D3.js
› WebStorm
推荐书目
› JavaScript 权威指南第 5 版
› Closure: The Definitive Guide
› Closure: The Definitive Guide
这是一个创建于 1421 天前的主题，其中的信息可能已经有所发展或是发生改变。
 |
1
Inf1nity 2021-01-02 12:37:47 +08:00  1
我只能想到用扫描数组，用哈希表存 <数,索引 list> 这个键值对，然后再扫一遍根据哈希表的 key 重建数组，重复元素索引这个时候也可以得到。
|
 |
2
shiji 2021-01-02 12:42:15 +08:00 via iPhone 1
能想到的是 O(n)
HashMap 键是 数组得每个值 值是 List<Integer> 存的是遇到重复的索引 |
|
3
shiji 2021-01-02 12:43:06 +08:00 via iPhone
尴尬了，手机打字慢 ，和楼上说的一样
|
 |
4
Jooooooooo 2021-01-02 13:28:45 +08:00 1
你要快就用空间换时间
弄个 map 出来 |
 |
5
Lemeng 2021-01-02 14:40:29 +08:00
楼顶的大佬说的不错
|
 |
6
hello2060 2021-01-02 18:30:10 +08:00
数组中每个元素读一遍 O(n)
找重用哈希每个元素 O(1) 全数组就是 O(n) 输出也是 O(n) 所以最后就是 O(n) |
 |
7
laminux29 2021-01-02 19:12:17 +08:00 1
关键在于 [较长] ，到底有多长，以及需要达到怎样的性能。这些参数不同，做法完全不一样。
比如，千万级别，性能 10 秒内，那么直接 for 循环，现在最新的 CPU 完全能扛得住。 数据量更大一些，同时需要考虑性能，此时按照楼上老哥们的方法，开始使用 map 等类似的数据结构，用空间换时间。 数据量再大一些，大到谷歌或百度这种级别，搜索引擎对 URL 进行唯一性判定的需求，那做法又完全变了，需要采用集群 + 分布式 hash 映射 + 允许一定量的重复计算并使用最终一致性。原理看似一句话，但下面设计到的成本控制、智慧运维、数据中间建设、通信问题等等，整个工程设计起来就相当复杂了。 |
 |
8
stevefan1999 2021-01-02 20:30:49 +08:00
hash tree, i.e. merkele tree, 也就是 bitcoin 用的那個
|
 |
9
xuanbg 2021-01-03 10:08:12 +08:00 1
再怎么长，也得遍历。所以时间复杂度最小也得 O(n)。你要是来个循环嵌套，那就是 O(n^2)。如果机灵一点把每个元素 hash 一下存到 hashmap 做 key，那么就不用嵌套循环了，每次都去 hashmap 里面找一下 key 存不存在，不存在就把自己存进去，存在就在另一个重复元素集合里面把自己的索引存进去。最后输出重复元素集合就行了。
|
Select Language