和 y = {y_i ： i elem [1，N]} 带有有序字母表。是否有可能找到最小的（如果有的话）对（i，j），使得x_i = y_j？
琐碎的 O（n^2） 时间 O（1） 空间算法只是让你将任一序列的每个元素进行比较，同时跟踪与序列开头的最小距离差异。
O（n log n） 时间 O（n） 空间算法只是对序列进行排序并进行比较，同时跟踪最小/最大的元素。
我想不出线性时间算法，我不确定这个问题会叫什么。
首先，请注意，可以通过仅对较小的列表进行排序，并在迭代较大列表时使用二叉搜索来在O(max{m,n}log(min{m,n}))中完成此操作。
此外，您可以使用哈希表将一个列表索引为配对x_i->min{j, x_j = x_i } - 这需要预期的线性时间和空间。
然后，只需迭代另一个列表，并在表中查找y_i，同时保持到目前为止找到的最小值。
在平均情况下，这总计为 O（n） 空间和时间。
伪代码：
table = {}
for each element x_i in x in ascending order of i:
if x_i is not in table:
table[x_i] = i
best_pair = (-1,-1)
for each element y_j in y:
if y_j in table:
if (table[y_j],j) is "better" than best_pair:
best_pair = (table[y_j], j)
return best_pair
我很确定它与元素区别性问题太相似了，无法在不使用哈希的情况下克服 Omega（nlogn） 边界，但没有想到任何证据。
一种选择是构建一个大小为 |Σ|的表，其中 Σ 是您的字母表，它将每个符号与它在字符串 x 中占据的第一个位置相关联。然后，您可以迭代 x，并为每个字符记录该字符在表中 x 中的第一个位置。然后，您可以传递字符串 y，对于 y 的每个字符，请查阅表以查找该字符首次出现在字符串 x 中的时间。你在问题中没有提到你是如何定义"最小"对的（字典顺序？最小化i + j？其他什么？），但你应该能够生成所有可能的对，然后在线性时间内取它们的最小值。
总的来说，这需要时间O（n + |Σ|）和使用空格O（|Σ|），所以如果你的字母表不是太大，这是相当快的。如果你的字母表很大，只需使用哈希表，这最终是预期的O（n）时间与O（n）空间。
O（n+m） algo：
- 从 i = 0 和 j = 0 开始
- 如果 x[i]
- 如果 x[i]> y[j] j++
- 如果 x[i] == y[j] => 你找到了它
显然，您还需要检查数组边界。