Как удалить дубликаты элементов в массиве в O (n) в C или C ++?

Question

Есть ли способ удалить дубликаты элементов в массиве в C / C ++ в O (n)?Предположим, что элементы равны a[5]={1,2,2,3,4}, тогда результирующий массив должен содержать {1,2,3,4} Решение может быть достигнуто с использованием двух циклов for, но я думаю, что это будет O (n ^ 2).

Answer 1

Если и только если исходный массив отсортирован, это можно сделать за линейное время:

std::unique(a, a + 5); //Returns a pointer to the new logical end of a.

В противном случае вам придется сначала выполнить сортировку, что составляет (99,999% времени)

Answer 2

Лучший случай - O(n log n). Выполните сортировку кучи для исходного массива: O(n log n) по времени, O(1) / по месту в пространстве. Затем последовательно пропустите массив с двумя индексами (source & dest), чтобы свернуть повторения. Это имеет побочный эффект не сохранения первоначального порядка, но, поскольку «удалить дубликаты» не указывает, какие дубликаты следует удалить (первый? Второй? Последний?), Я надеюсь, что вам все равно, что заказ потерян .

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

Любой, кто утверждает, что это может быть сделано в O(n) время и на месте, просто неправ, по модулю некоторые аргументы о том, что означает O(n) и на месте. Одно очевидное псевдо-решение, если ваши элементы представляют собой 32-разрядные целые числа, - это использование 4-гигабитного битового массива (размером 512 мегабайт), инициализированного для всех нулей, при включении, когда вы видите это число, при включении немного бит был уже включен. Конечно, тогда вы используете тот факт, что n ограничен константой, так что технически все это O(1), но с ужасным постоянным фактором. Однако я упоминаю этот подход, поскольку, если n ограничен небольшой константой - например, если у вас есть 16-разрядные целые числа - это очень практичное решение.

Answer 3

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

Вместо хеш-таблицы идея заключается в использовании битового вектора.Это требование к памяти O (1), которое теоретически должно радовать Рахула (но не будет).С 32-разрядными целыми числами для битового вектора потребуется 512 МБ (т. Е. 2 ​​** 32 бита) - при условии 8-разрядных байтов, как может указывать какой-то педант.

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

Псевдокод для полноты...

src = dest = input.begin ();
while (src != input.end ())
{
  if (!bitvector [*src])
  {
    bitvector [*src] = true;
    *dest = *src; dest++;
  }
  src++;
}
//  at this point, dest gives the new end of the array

Просто чтобы быть по-настоящему глупым (но теоретически правильным), я также укажу, что требования к пространству все еще составляют O (1), даже если массив содержит 64-битные целые числа.Я согласен, постоянный термин немного велик, и у вас могут быть проблемы с 64-битными процессорами, которые не могут фактически использовать полные 64-битные адреса, но ...

Answer 4

Да. Поскольку доступ (вставка или поиск) в хеш-таблице - это O (1), вы можете удалить дубликаты в O (N).

псевдокод:

hashtable h = {}
numdups = 0
for (i = 0; i < input.length; i++) {
    if (!h.contains(input[i])) {
        input[i-numdups] = input[i]
        h.add(input[i])
    } else {
        numdups = numdups + 1
    }

Это O (N).

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

Answer 5

Каноническая реализация алгоритма unique() выглядит примерно так:

template<typename Fwd>
Fwd unique(Fwd first, Fwd last)
{
    if( first == last ) return first;
    Fwd result = first;
    while( ++first != last ) {
        if( !(*result == *first) )
            *(++result) = *first;
    }
    return ++result;
}

Этот алгоритм принимает диапазон отсортированных элементов. Если диапазон не отсортирован, отсортируйте его перед вызовом алгоритма. Алгоритм будет работать на месте и вернет итератор, указывающий на элемент «один за последним последним» уникальной последовательности.

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

Этот алгоритм работает в режиме O (n). Это о-о-о, наихудший случай во всех случаях, а не амортизированное время. Он использует O (1) пробел.

Answer 6

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

Если вы найдете целое число, например 3, включите 3-й бит. Если вы найдете целое число, например 5, включите 5-й бит.

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

Answer 7

В качестве примера вы привели отсортированный массив. Это возможно только в этом случае (учитывая ваше постоянное ограничение пространства)