找出数组 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

所以我应该写一个 returns 4 但时间复杂度为 O(N) 的方法

我想到了时间复杂度为 O(N2) 和 O(NLogN) 的解决方案

Answer 1

使用哈希 table 并进行线性扫描。

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

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

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)。