Проверка дубликатов в векторе

Возможный дубликат:
Определение, если неупорядоченный вектор <T> имеет все уникальные элементы

Мне нужно проверить вектор для дубликатов. Каков наилучший способ приблизиться к этому:

Я беру первый элемент, сравниваю его со всеми другими элементами вектора. Затем возьмите следующий элемент и сделайте то же самое и так далее.

Это лучший способ сделать это, или есть более эффективный способ проверить наличие дубликатов?

Ответы

Ответ 1

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

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

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

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

Ответ 2

Если ваш вектор является контейнером STL, решение легко:

  • первая сортировка
  • затем 'unique'

Например:

std::sort   ( myvec.begin(), myvec.end());
std::unique ( myvec.begin(), myvec.end());

Обратите внимание, что std:: unique фактически не удаляет дубликаты, а переносит их в конец контейнера и возвращает итератор в первый дубликат. Поэтому в зависимости от ситуации вы можете использовать std:: remove для удаления хвоста контейнера или использовать std:: copy для копирования только не дубликатов в другой контейнер.

Ответ 3

Сортировка, а затем сравнение смежных элементов - путь. Сорт принимает O (n log n) сравнения, а затем дополнительный n-1 для сравнения соседних элементов.

Схема в вопросе примет (n ^ 2)/2 сравнения.

Ответ 4

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