algorithm - 查找列表中唯一的非唯一元素对之间的最小距离

Question

(不是作业)

我有一个包含重复元素的列表: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)

我不喜欢因为

1. 需要 O(u•n) 搜索唯一项目的索引出现
2. 是 O(u•o•(n-o))，其中 u 和 o 是唯一项及其出现

使用示例文本 blob 是:

1. 74500 检查出现情况
2. 250000 跳过比较
3. 247582 排序对，散列，从 map 获取，比较

Answer 1

这是一个更简单、更快的算法。假设列表在数组 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]。
  • 设置 last[X[i]] = i。

这具有最小的空间复杂度 O(u^2) 和我怀疑也是最小的时间复杂度 O(u^2 + un)。

[编辑:根据要求，我们现在只报告“任一方向”的一对元素之间的最小距离，而不是在两个方向上分别报告。还在 n < u 的情况下为时间复杂度添加了一个 u^2 项，尽管听起来我们从根本问题中保证 n >= u。]