algorithm - 最快稳定的去重算法

Question

我有一个数组，我需要从它的数组中取出，不要重复。我必须在原始数组中保留那些具有最小顺序的唯一元素。大概就是这个意思

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]

Answer 1

在遍历数组时，将遇到的每个(唯一)元素放入哈希表或树中。这将使您能够在检查第 k 元素时快速检查您是否在前面的 k-1 元素中遇到了相同的数字。

一棵树会给你整体 O(n log(n)) 时间复杂度。具有良好哈希函数的哈希表会做得更好(可能 O(n))。