Можно создать дубликат:
Determining if an unordered vector<T> has all unique elementsПроверка дубликатов в векторе
Я должен проверить вектор для дублей. Каков наилучший способ приблизиться к этому:
Я беру первый элемент, сравниваю его со всеми другими элементами в векторе. Затем возьмите следующий элемент и сделайте то же самое и так далее.
Это лучший способ сделать это, или есть более эффективный способ проверить наличие дубликатов?
Используйте hash table, в который вы вставляете каждый элемент. Прежде чем вставлять элемент, проверьте, есть ли он там. Если это так, у вас есть дубликат. Это O(n)в среднем, но худший случай так же плох, как и ваш текущий метод.
В качестве альтернативы вы можете использовать set, чтобы сделать то же самое в O(n log n) наихудшем случае. Это так же хорошо, как решение для сортировки, за исключением того, что оно не изменяет порядок элементов (использует больше памяти, хотя с момента создания набора).
Другой способ - скопировать вектор в другой вектор, отсортировать его и проверить смежные элементы. Я не уверен, что это быстрее, чем установленное решение, но я думаю, что сортировка добавляет меньше накладных расходов, чем сбалансированные деревья поиска, которые использует набор, поэтому на практике это должно быть быстрее.
Конечно, если вы не заботитесь о сохранении первоначального порядка элементов, просто отсортируйте начальный вектор.
Не совсем «как хорошо», как решение для сортировки. Это тот же самый порядок выполнения, но постоянный фактор при сортировке вектора, который, как гарантируется, имеет свои элементы, смежные в памяти, будет значительно меньше, чем алгоритм с использованием набора. Я бы не удивился, если бы он был в два раза быстрее. +1 в любом случае. Думаю, у вас есть лучший ответ. –
@A. Леви: правда, я упомянул еще один метод. – IVlad
Сортировка Radix может быть даже быстрее, чем O (n log n). http://en.wikipedia.org/wiki/Radix_sort –
Сортировка, а затем сравнение смежных элементов - путь. Сорт принимает O (n log n) сравнения, а затем дополнительный n-1 для сравнения соседних элементов.
Схема в вопросе займет (n^2)/2 сравнения.
Если вектор представляет собой STL контейнер, раствор легко:
Например:
std::sort (myvec.begin(), myvec.end());
std::unique (myvec.begin(), myvec.end());
Обратите внимание, что std :: unique фактически не удаляет дубликаты, а переносит их в конец контейнера и возвращает itera к первому дублируемому. Так что в зависимости от ситуации вы можете использовать std :: remove для удаления хвоста контейнера или использовать std :: copy для копирования только не дубликатов в другой контейнер.
Чтобы уточнить, дубликаты не перемещаются в конец диапазона; они просто удаляются с передней части диапазона. Значения элементов после нового конца, возвращаемые 'std :: unique()', не определены. Если вы хотите проверить, не содержит ли пробел дубликатов, 'std :: nearby_find()' более эффективен, чем использование 'std :: unique()'. –
Вы правы. Std :: unique сначала помещает все уникальные элементы и не указывает, что происходит с остальной частью контейнера. Самое главное, однако, помнить, что вы должны использовать возвращенный итератор, а не предполагать, что ваш контейнер содержит только уникальные элементы. Вы должны вручную очистить хвост контейнера. – Patrick
Вы также можете использовать binary_search.
Вот два хороших примеров, которые помогут вам:
Если вы не заботитесь о случайные ложных срабатываний, вы можете использовать Bloom Filter обнаружить возможные дубликаты Коллекция. Если ложные срабатывания не могут быть приняты, возьмите значения, которые выходят из фильтра, и пропустите второй проход обнаружения. Список неудачных значений должен быть довольно небольшим, хотя их нужно будет проверить на полный ввод.
Дубликат [Определение, если неупорядоченный вектор имеет все уникальные элементы] (http://stackoverflow.com/questions/2769174/determining-if-an-unordered-vectort-has-all-unique-elements) –
Can вы меняете вектор? Если нет, у вас есть память для размещения копии? – florin