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 存不存在,不存在就把自己存进去,存在就在另一个重复元素集合里面把自己的索引存进去。最后输出重复元素集合就行了。
|