Самый быстрый стабильный алгоритм удаления дубликатов

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)).

Answer 2

Если область элементов конечна (и не слишком велика), вы можете выполнить двоичную счетную сортировку. Это было бы O (n).

В противном случае вы можете использовать временную таблицу Hashtable для хранения элементов во время итерации по массиву и помещать элемент в выходной массив только в том случае, если элемент в данный момент отсутствует в хеш-таблице. Это было бы O (n) в типичном случае.

Answer 3

Если вам не нужно пространство O (1), просто создайте массив индексов для элементов исходного массива (изначально 0,1,2, ..., n-1) и отсортируйте их, используя номер индекса для разрешения сравнений между элементами, которые в противном случае сравниваются равными. Это стандартный метод построения стабильной сортировки поверх нестабильной сортировки. После этого вы просто просматриваете массив индексов, чтобы найти элементы, которые хотите удалить из исходного массива.

Answer 4

Вам разрешено делать вещи на месте и сортировать массив? Если вы делаете это очень просто:

sort(array) // use a stable sorting algorithm of your choice.
i = 0 //how many unique elements we have already spotted
j = 0 //how many array elements we have checked

while(j < arr.length){
    //found a new value:
    array[i] = array[j];

    //find next value in array that is different
    while(j < arr.length && array[i] == array[j]){
        j++;
    }
}
arr.length = i;

---

Если вам нужно самостоятельно реализовать алгоритм устойчивой сортировки, возможно, самым простым является Mergesort.

Однако в этом случае вы можете вместо этого напрямую адаптировать процедуру слияния, чтобы игнорировать похожие значения (отдавая приоритет более ранним), вместо того, чтобы возвращать все из них.