找到數組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）複雜性。