Как сделать элементы вектора уникальными? (удалить несмежные дубликаты) - PullRequest
Новая
       21

Как сделать элементы вектора уникальными? (удалить несмежные дубликаты)

34 голосов
/ 21 сентября 2009

У меня есть вектор, содержащий несколько несмежных дубликатов.

В качестве простого примера рассмотрим: 

2 1 6 1 4 6 2 1 1

Я пытаюсь сделать это vector уникальным, удаляя несмежные дубликаты и поддерживая порядок элементов.

Результат будет: 

2 1 6 4

Решения, которые я попробовал:

  1. Вставка в std :: set, но проблема этого подхода в том, что он нарушит порядок элементов.
  2. Используйте комбинацию std :: sort и std :: unique. Но опять та же проблема порядка.

  3. Удаление дубликатов вручную: 

        Define a temporary vector TempVector.
    for (each element in a vector)
    {
        if (the element does not exists in TempVector)
        {
            add to TempVector;
        }
    }
    swap orginial vector with TempVector.

Мой вопрос:

Есть ли алгоритм STL, который может удалять несмежные дубликаты из вектора? в чем его сложность?

Ответы [ 11 ]

0 голосов
/ 11 августа 2017

Учитывая, что ваш ввод в vector<int> foo, вы можете использовать remove, чтобы выполнить работу для вас здесь, тогда, если вы хотите уменьшить вектор, просто используйте erase в противном случае просто используйте last в качестве итератора «один за другим», если вы хотите удалить вектор с дубликатами, но сохранить порядок: 

auto last = end(foo);

for(auto first = begin(foo); first < last; ++first) last = remove(next(first), last, *first);

foo.erase(last, end(foo));

Живой пример

Насколько сложность времени это будет O (нм) . Где n - количество элементов, а m - количество уникальных элементов. Что касается сложности пространства, для этого будет использоваться O (n) , поскольку оно выполняет удаление на месте.

Страница:
...