(不是作业)
我有一个包含重复元素的列表:A B C B A D C B
我想要每两个无序元素之间的最短距离:
(A B): 1
(A C): 2
(A D): 1
(B C): 1
(B D): 2
(C D): 1
我能否提高当前实现的复杂性?元素是单词,搜索空间是段落,所以我预计长度为 ~200 的列表中有 ~100 个唯一元素。
我的实现:
pairs <= map(pair, distance)
For each unique element 'me'
1. \ For each index 'o' of me in list
2. \ For each 'item' at index 'i' in the list
| if (item == me) skip
| pair <= sort(me, item)
| distance <= abs(i - o)
| existing <= dist(pair in pairs), or infinity
\ if (distance < existing) pairs <= (pair, distance)
我不喜欢因为
- 需要
O(u•n)
搜索唯一项目的索引出现 - 是
O(u•o•(n-o))
,其中u
和o
是唯一项及其出现
使用示例文本 blob 是:
74500
检查出现情况250000
跳过比较247582
排序对,散列,从 map 获取,比较
最佳答案
这是一个更简单、更快的算法。假设列表在数组 X[] 中:
- 初始化一个二维数组 best[i][j] 以包含所有 1 <= i < j <= u 的 INF。
- 初始化数组 last[i] 以包含所有 1 <= i <= u 的 -INF。
- 对于每个位置 i:
- 对于每个元素类型 j:
- 如果 j != X[i]:
- 设 x = min(j, X[i]) 和 y = max(j, X[i])。
- 如果 i - last[j] < best[x][y] 则将 best[x][y] 更新为 i - last[j]。
- 如果 j != X[i]:
- 设置 last[X[i]] = i。
- 对于每个元素类型 j:
这具有最小的空间复杂度 O(u^2) 和我怀疑也是最小的时间复杂度 O(u^2 + un)。
[编辑:根据要求,我们现在只报告“任一方向”的一对元素之间的最小距离,而不是在两个方向上分别报告。还在 n < u 的情况下为时间复杂度添加了一个 u^2 项,尽管听起来我们从根本问题中保证 n >= u。]
关于algorithm - 查找列表中唯一的非唯一元素对之间的最小距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24636159/