Алгоритм. Как эффективно удалять повторяющиеся элементы в списке?

Ответ 1

Предполагая порядок:

• Создать пустой набор S и пустой список M.
• Проверять список L по одному элементу за раз.
• Если элемент находится в наборе S, пропустите его.
• В противном случае добавьте его в M и S.
• Повторить для всех элементов в L.
• Return M.

В Python:

>>> L = [2, 1, 4, 3, 5, 1, 2, 1, 1, 6, 5]
>>> S = set()
>>> M = []
>>> for e in L:
...     if e in S:
...         continue
...     S.add(e)
...     M.append(e)
... 
>>> M
[2, 1, 4, 3, 5, 6]

Если порядок не имеет значения:

M = list(set(L))

Ответ 2

Специальный случай: Хеширование и равенство

Во-первых, нам нужно что-то определить о предположениях, а именно о существовании равенства и имеет отношение функций. Что я имею в виду? Я имею в виду, что для множества исходных объектов S, учитывая любые два объекта x1 и x2, являющиеся элементами S, существует (хэш-функция) F такая, что:

if (x1.equals(x2)) then F(x1) == F(x2)

Java имеет такие отношения. Это позволяет вам проверять дубликаты как операцию O (1) и, таким образом, сводит алгоритм к простой проблеме O (n). Если заказ неважен, это простой один вкладыш:

List result = new ArrayList(new HashSet(inputList));

Если порядок важен:

List outputList = new ArrayList();
Set set = new HashSet();
for (Object item : inputList) {
  if (!set.contains(item)) {
    outputList.add(item);
    set.add(item);
  }
}

Вы заметите, что я сказал "около O (1)". Это потому, что такие структуры данных (как Java HashMap или HashSet) полагаются на метод, в котором часть хэш-кода используется для поиска элемента (часто называемого ведром) в хранилище резервных копий. Количество ведер - это мощность 2. Таким образом, индекс в этот список легко вычислить. hashCode() возвращает int. Если у вас есть 16 ведер, вы можете найти, какой из них использовать ANDing hashCode с 15, давая вам число от 0 до 15.

Когда вы пытаетесь поместить что-то в это ведро, оно уже может быть занято. Если это так, произойдет сравнение linear всех записей в этом ковше. Если скорость столкновения становится слишком высокой или вы пытаетесь установить слишком много элементов в структуре, она будет увеличена, как правило, удваивается (но всегда с помощью силы-2), и все элементы помещаются в их новые ведра (на основе новой маски). Таким образом, изменение размеров таких структур относительно дорого.

Поиск также может быть дорогостоящим. Рассмотрим этот класс:

public class A {
  private final int a;

  A(int a) { this.a == a; }

  public boolean equals(Object ob) {
    if (ob.getClass() != getClass()) return false;
    A other = (A)ob;
    return other.a == a;
  }

  public int hashCode() { return 7; }
}

Этот код является совершенно законным и выполняет контракт equals-hashCode.

Предполагая, что ваш набор содержит ничего, кроме экземпляров A, ваша вставка/поиск теперь превращается в операцию O (n), превращая всю вставку в O (n ²).

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

Наконец, надо сказать, что это особый случай. Если вы используете язык без такого "хэширующего ярлыка", то это другая история.

Общий случай: нет заказа

Если для списка нет функции упорядочения, вы зацикливаетесь на сравнении грубой силы O (n ²) каждого объекта с каждым другим объектом. Итак, на Java:

List result = new ArrayList();
for (Object item : inputList) {
  boolean duplicate = false;
  for (Object ob : result) {
    if (ob.equals(item)) {
      duplicate = true;
      break;
    }
  }
  if (!duplicate) {
    result.add(item);
  }
}

Общий случай: Заказ

Если существует функция упорядочения (как, например, список целых чисел или строк), вы сортируете список (это O (n log n)), а затем сравниваете каждый элемент в списке со следующим ( O (n)), поэтому полный алгоритм O (n log n). В Java:

Collections.sort(inputList);
List result = new ArrayList();
Object prev = null;
for (Object item : inputList) {
  if (!item.equals(prev)) {
    result.add(item);
  }
  prev = item;
}

Примечание: приведенные выше примеры не предполагают, что в списке нет нулей.

Ответ 3

Если порядок не имеет значения, вы можете попробовать этот алгоритм, написанный на Python:

>>> array = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6]
>>> unique = set(array)
>>> list(unique)
[1, 2, 3, 4, 5, 6]

Ответ 4

в haskell это будет покрываться функциями nub и nubBy

nub :: Eq a => [a] -> [a]
nub [] = []
nub (x:xs) = x : nub (filter (/= x) xs)

nubBy :: (a -> a -> Bool) -> [a] -> [a]
nubBy f [] = []
nubBy f (x:xs) = x : nub (filter (not.f x) xs)

nubBy ослабляет зависимость от Eq typeclass, вместо этого позволяет вам определять свою собственную функцию равенства для фильтрации дубликатов.

Эти функции работают над списком согласованных произвольных типов (например, [1,2,"three"] не допускается в haskell), и оба сохраняют порядок.

Чтобы сделать это более эффективным, использование Data.Map(или реализация сбалансированного дерева) может использоваться для сбора данных в набор (ключ - это элемент, а значение - индекс в исходный список, чтобы иметь возможность вернуть исходный заказ), затем собирать результаты обратно в список и сортировать по индексу. Я попытаюсь реализовать это позже.

import qualified Data.Map as Map

undup x = go x Map.empty
    where
        go [] _ = []
        go (x:xs) m case Map.lookup x m of
                         Just _  -> go xs m
                         Nothing -> go xs (Map.insert x True m)

Это прямой перевод решения @FogleBird. К сожалению, он не работает без импорта.

a Очень простая попытка заменить Data.Map import - реализовать дерево, что-то вроде этого

data Tree a = Empty
            | Node a (Tree a) (Tree a)
            deriving (Eq, Show, Read)

insert x Empty = Node x Empty Empty
insert x (Node a left right)
    | x < a = Node a (insert x left) right
    | otherwise = Node a left (insert x right)

lookup x Empty = Nothing --returning maybe type to maintain compatibility with Data.Map
lookup x (Node a left right)
    | x == a = Just x
    | x < a = lookup x left
    | otherwise = lookup x right

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

Я беру запросы, кажется. В ответ на запрос @Jonno_FTWs это решение, которое полностью удаляет дубликаты из результата. Это не совсем не похоже на оригинал, просто добавив лишний случай. Однако производительность во время выполнения будет намного медленнее, так как вы проходите через каждый дополнительный список дважды, один раз для elem и второй раз для ретуширования. Также обратите внимание, что теперь он не будет работать в бесконечных списках.

nub [] = []
nub (x:xs) | elem x xs = nub (filter (/=x) xs)
           | otherwise = x : nub xs

Интересно, что вам не нужно фильтровать второй рекурсивный случай, потому что elem уже обнаружил, что дубликатов нет.

Ответ 5

В java это один лайнер.

Set set = new LinkedHashSet(list);

предоставит вам коллекцию с удаленными элементами.

Ответ 6

В Python

>>> L = [2, 1, 4, 3, 5, 1, 2, 1, 1, 6, 5]
>>> a=[]
>>> for i in L:
...   if not i in a:
...     a.append(i)
...
>>> print a
[2, 1, 4, 3, 5, 6]
>>>

Ответ 7

Для Java может пойти с этим:

private static <T> void removeDuplicates(final List<T> list)
{
    final LinkedHashSet<T> set;

    set = new LinkedHashSet<T>(list); 
    list.clear(); 
    list.addAll(set);
}

Ответ 8

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

для индексов простоты для элементов может храниться в виде std:: map

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

Ответ 9

Это зависит от того, что вы подразумеваете под "эффективным". Наивный алгоритм - O (n ^ 2), и я предполагаю, что вы на самом деле имеете в виду, что вы хотите что-то более низкого порядка, чем это.

Как говорит Maxim100, вы можете сохранить заказ, объединив список с серией чисел, используйте любой алгоритм, который вам нравится, а затем верните остаток обратно в исходный порядок. В Haskell это будет выглядеть так:

superNub :: (Ord a) => [a] -> [a]
superNub xs = map snd 
              . sortBy (comparing fst) 
              . map head . groupBy ((==) `on` snd) 
              . sortBy (comparing snd) 
              . zip [1..] $ xs

Конечно, вам нужно импортировать Data.List(сортировка), Data.Function(on) и Data.Ord(сравнение). Я мог бы просто прочесть определения этих функций, но в чем смысл?

Ответ 10

Удалить дубликаты в списке inplace в Python

Случай. Элементы в списке не являются хешируемыми или сопоставимыми

То есть мы не можем использовать set (dict) или sort.

from itertools import islice

def del_dups2(lst):
    """O(n**2) algorithm, O(1) in memory"""
    pos = 0
    for item in lst:
        if all(item != e for e in islice(lst, pos)):
            # we haven't seen `item` yet
            lst[pos] = item
            pos += 1
    del lst[pos:]

Случай: элементы хешируются

Решение взято из здесь:

def del_dups(seq):
    """O(n) algorithm, O(log(n)) in memory (in theory)."""
    seen = {}
    pos = 0
    for item in seq:
        if item not in seen:
            seen[item] = True
            seq[pos] = item
            pos += 1
    del seq[pos:]

Случай. Элементы сопоставимы, но не хешируются

То есть мы можем использовать sort. Это решение не сохраняет первоначальный порядок.

def del_dups3(lst):
    """O(n*log(n)) algorithm, O(1) memory"""
    lst.sort()
    it = iter(lst)
    for prev in it: # get the first element 
        break
    pos = 1 # start from the second element
    for item in it: 
        if item != prev: # we haven't seen `item` yet
            lst[pos] = prev = item
            pos += 1
    del lst[pos:]

Ответ 11

Я написал алгоритм для строки. На самом деле неважно, какой у вас тип.

static string removeDuplicates(string str)
{
    if (String.IsNullOrEmpty(str) || str.Length < 2) {
        return str;
    }

    char[] arr = str.ToCharArray();
    int len = arr.Length;
    int pos = 1;

    for (int i = 1; i < len; ++i) {

        int j;

        for (j = 0; j < pos; ++j) {
            if (arr[i] == arr[j]) {
                break;
            }
        }

        if (j == pos) {
            arr[pos] = arr[i];
            ++pos;
        }
    }

    string finalStr = String.Empty;
    foreach (char c in arr.Take(pos)) {
        finalStr += c.ToString();
    }

    return finalStr;
}

Ответ 12

Однострочное решение в 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)

Ответ 13

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

Ответ 14

Мой код в 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 - количество уникальных членов входного списка

Ответ 15

Алгоритм 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

*//на основе 'value' сортировать массив temp. *

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

//на основе "ключа" сортировать массив temp.//construct массив p с помощью temp.

p[i]=temp[i].value

return p

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