在阵列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（2）计算新的最大值。max将包含答案。O（N）复杂性。