阵列O(N)相关性检验中重复元素间的差异

Question

我已经通过了一个亲切的测试，它要求我编写一个函数来找出重复元素之间的最大差异。例如，如果我有一个N元素数组，AI=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)计算新的最大值。马克斯会给出答案。O(N)总体复杂性。