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

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

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

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