我有一个数组,我需要从它的数组中取出,不要重复。我必须在原始数组中保留那些具有最小顺序的唯一元素。大概就是这个意思
NoDuplicate(A, value)
for int i = 0 to i < A.length
if A[i] == value
return true
i++
return false
StableRemoveAlgo(A)
for int i = 0 to i < A.length
if NoDuplicate(result, A[i])
result.append(A[i])
return result
是否有比这个简单算法更快的算法?
更新:我无法对数组进行排序。我需要一个“稳定”版本的重复删除算法。所以,如果 A[i] == A[j] and i < j
算法必须删除元素 A[j]
最佳答案
在遍历数组时,将遇到的每个(唯一)元素放入哈希表或树中。这将使您能够在检查第 k
元素时快速检查您是否在前面的 k-1
元素中遇到了相同的数字。
一棵树会给你整体 O(n log(n))
时间复杂度。具有良好哈希函数的哈希表会做得更好(可能 O(n)
)。
关于algorithm - 最快稳定的去重算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5913677/