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

Да. Поскольку доступ (вставка или поиск) к хеш-таблице - 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), чтобы удовлетворить теоретиков.

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

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

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

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

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

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

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

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 бита адреса, но ...

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

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

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

Каноническая реализация алгоритма 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).

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