#c #vector
#c #вектор
Вопрос:
У меня есть вектор с разными значениями, и некоторые из них могут отображаться дважды. (Только дважды.)
Как я могу найти ПЕРВЫЙ дубликат элемента?
Например: [a][b][b][a]
Тогда мне понадобится ‘b’.
(Извините за вопрос новичка.)
Комментарии:
1. если вы знаете значения элементов, скажем, их алфавит, у вас может быть вектор<int> vec(26); и для каждого значения вы выполняете vec[c-‘a’] ; и если оно не равно нулю, то значение появилось дважды. Это быстрее, чем при использовании std::set . Но тогда вы должны быть уверены, каковы значения.
Ответ №1:
Если вы ищете смежные дубликаты, вы можете просто использовать std::adjacent_find .
Если дубликаты не обязательно соседние, то вы могли бы сначала (См. Комментарий @aix ниже) std::sort создать вектор, а затем использовать std::adjacent_find для результата.
В качестве альтернативы, вы могли бы поместить каждый элемент в std::set и по ходу выполнения искать столкновения.
Комментарии:
1. ( 1) Метод сортировки не обязательно будет находить первый дублированный элемент, как того требует вопрос.
Ответ №2:
На этот вопрос есть много ответов. Чтобы найти лучший элемент, необходимо знать контекст вашего сценария использования. Например, нормально ли, что дубликаты существуют в первую очередь? Что вы собираетесь делать с результатом поиска дубликатов? Можем ли мы всегда использовать параллельную структуру с вектором? И многое другое…
Итак, один из многих способов — повторить элементы и insert их в std::set<> . Посмотрите на second параметр возвращаемого std::pair<> , чтобы узнать, существовало ли значение в наборе или нет, тогда вы получите первый дубликат и сможете отказаться от set добавления.
Ответ №3:
Если вы не хотите использовать дополнительное хранилище, есть примерно два решения. Первый — это перебор: для каждого элемента i проверьте, равен ли он элементам 0..i-1. Это O(N*N) (очевидный наихудший случай: последние два элемента являются первыми дубликатами).
Второе решение — ускорить поиск, сохранив диапазон 0 ..i. отсортированным. Вы обнаружите дубликаты тривиально во время сортировки. Пузырьковая сортировка эффективна, потому что диапазон 0..i-1 уже был отсортирован на предыдущей итерации. Все еще O(N*N) худший случай, но O(N) если диапазон был отсортирован раньше.