最快的稳定重复删除算法

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-th元素时快速检查是否在前面的k-1元素中遇到了相同的数字.

树会给你整体O(n log(n))时间复杂性.具有良好散列函数的散列表可以做得更好(可能O(n)).