Блог

У меня есть массив, и мне нужно получить из него массив без дубликатов. Я должен оставить те уникальные элементы, которые имеют минимальный порядок в исходном массиве. Примерно это я имею в виду

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

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

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

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

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

 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 amp;amp; array[i] == array[j]){
        j  ;
    }
}
arr.length = i;
  

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

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