找到数组O（N）中的重复元素之间的差异亲切性测试

Question

我已经通过了一个亲切性测试，要求我编写一个函数来查找重复元素之间差异的最大值。 例如，如果我有N个单元A的阵列[I] = K其中K < = N

A[0]=1 
A[1]=6 
A[2]=1 
A[3]=2 
A[4]=3 
A[5]=6 
A[6]=2 

这里是重复的元素之间的差的最大值为4（5-1 = 4），因为

A[1]=A[5] the difference =5-1=4 
A[0]=A[2] the difference =2-0=2 
A[3]=A[6] the difference =6-3=3 

最大为4

所以我应该写一个返回4但随着时间复杂度为O（N），其

的解决方案，来我的脑海里有一个方法时间复杂度O（N2）和O（NLogN）

Answer 1

使用散列表并进行线性扫描。

在表中存储元素的第一个出现。如果您再次看到它，请计算差异并根据需要更新全局最大值。

注意：如果您知道元素范围有限，也可以使用数组。

Answer 2

我以前做过这样的事情。

制作这个容器：

int max = 0; 
map<int, list<int>> 

的想法是，你遍历列表和值添加到地图，当你看到它。该列表包含您发现元素时的数组索引。

即6的地图应该包含1-> 5。每次迭代（如果列表大小> 1）计算：curIndex - *--list.end() - O（1）。如果此值大于最大值，请更新最大值。 O（N）迭代列表，O（1）检查列表大小，O（1）计算新的最大值。 Max将包含答案。 O（N）复杂性。