数组中最远的相等元素

Question

假设您有一个未排序的数组，您将如何找到 2 个相等的元素，使它们在数组中最远。例如8 7 3 4 7 5 3 9 3 7 9 0， ans 将是7(9) - 7(1) = 8。我想到了以下几点

initialise max = 0
using hashing, store the elements along with its index
whenever there is a collision, compare the current index with the hashed one
if it is greater, set max = current index - hashed one and copy element along with index to some other location.

在时间 - O(n) 和空间 - O(n) 中运行。这样对吗？有没有更好的解决办法。

Answer 1

O(n) 运行时间和 O(n) 空间似乎是最佳的 AFAIK。

这是Python的实现：

#!/usr/bin/python
hashindex = {}

l = [8,7,3,4,7,5,3,9,3,7,9,0]

max_diff = 0
value = 0

for i in range(len(l)):
    indices = hashindex.get(l[i], None)
    if indices:
        hashindex[l[i]] = (indices[0], i)
    else:
        hashindex[l[i]] = (i, i)
    diff = hashindex[l[i]][1] - hashindex[l[i]][0]
    if diff > max_diff:
        max_diff = diff
        value = l[i]

print max_diff, value