Алгоритм - Как эффективно удалить дубликаты элементов в списке?

Question

Есть список L . Он содержит элементы произвольного типа каждый . Как эффективно удалить все дублирующиеся элементы в таком списке? ЗАКАЗ должен быть сохранен

Требуется только алгоритм, поэтому импорт любой внешней библиотеки не разрешен.

Похожие вопросы

• В Python, какой самый быстрый алгоритм удаления дубликатов из списка, чтобы все элементы были уникальными при сохранении порядка ?

• Как удалить дубликаты из списка в Python при сохранении порядка?

• Удаление дубликатов из списка списков в Python

• Как удалить дубликаты из списка в Python?

Answer 1

• просмотреть список и назначить последовательный индекс каждому элементу
• сортировка списка по некоторой функции сравнения для элементов
• удалить дубликаты
• сортировка списка по назначенным индексам

для простоты индексы для предметов могут храниться в чем-то вроде std :: map

выглядит как O (n * log n), если я ничего не пропустил

Answer 2

Алгоритм delete_duplicates (a [1 .... n])

// Удалить дубликаты из данного массива

// входные параметры: a [1: n], массив из n элементов

{

temp[1:n]; // массив из n элементов

 temp[i]=a[i];for i=1 to n

     temp[i].value=a[i]

        temp[i].key=i

* // на основе 'значения' сортировать массив температур. *

// на основе 'значения' удалить повторяющиеся элементы из темп.

// на основе ключа сортировать массив temp. // построить массив p, используя temp.

p[i]=temp[i].value

return p

В других элементах поддерживается в выходном массиве с помощью «ключа». Предположим, ключ имеет длину O (n), время, необходимое для выполнения сортировки ключа, и значение равно O (nlogn). Таким образом, время, необходимое для удаления всех дубликатов из массива, составляет O (nlogn).

Answer 3

Мой код на Java:

ArrayList<Integer> list = new ArrayList<Integer>();

list.addAll({1,2,1,3,4,5,2,3,4,3});

for (int i=0; i<list.size(); i++)
{
    for (int j=i+1; j<list.size(); j++)
    {
        if (list.get(i) == list.get(j))
        {
            list.remove(i);
            j--;
        }
    }
}

или просто сделайте это:

SetList<Integer> unique = new SetList<Integer>();

unique.addAll(list);

В обоих случаях время = nk ~ O (n ^ 2)

где n - размер списка ввода,

k - количество уникальных членов списка ввода

Answer 4

Может быть, вам стоит рассмотреть использование ассоциированных массивов (он же dict в python), чтобы избежать дублирования элементов.

Answer 5

Однострочное решение в Python .
Используя списки-понимание:

>>> L = [2, 1, 4, 3, 5, 1, 2, 1, 1, 6, 5]
>>> M = []
>>> zip(*[(e,M.append(e)) for e in L if not e in M])[0]
(2, 1, 4, 3, 5, 6)