MiddleКодИногдаЕщё не отвечали
Найдите уникальный элемент в контейнере за один проход
Верните первый элемент, встречающийся ровно один раз в обобщённом контейнере, или «нет результата», если все элементы повторяются.
Требования:
проход. (Для частного случая «все дубликаты встречаются ровно дважды» существует и решение одним XOR-проходом с O(1) памяти.)
- O(n) время. Постройте счётчики за один проход, затем верните первый count==1.
- Используйте
std::optionalдля возврата «может не существовать». - Честно считайте проходы: второй просмотр для поиска записи — это второй
template<typename Container>
std::optional<typename Container::value_type>
findFirstUnique(const Container& c) {
// ваш код здесь
}Допишите реализацию.
Если все элементы — целые и каждый повторяющийся встречается ровно дважды, XOR всех значений: a^a=0, остаётся уникальный — O(n) времени, O(1) памяти. В общем случае: за один проход построить unordered_map<T,int> счётчиков, затем вернуть запись с count==1.
- ✗Называть решение 'однопроходным', когда второй просмотр карты/множества — это второй проход
- ✗Использовать сортировку — требует двух проходов или O(n log n)
- ✗Не уточнять ограничения задачи перед выбором алгоритма
- →Как найти первый неповторяющийся символ в строке за один проход?
- →Что делать, если элементы могут встречаться любое число раз и нужен тот, у которого нечётное количество?
Оглавление
Задача
Реализуйте функцию, которая находит первый уникальный (встречающийся ровно один раз) элемент в контейнере.
Решение
#include <vector>
#include <string>
#include <unordered_map>
#include <optional>
#include <cassert>
// Подход: один проход для подсчёта + один проход для поиска
// (два логических прохода, но O(n) суммарно)
template<typename Container>
std::optional<typename Container::value_type>
findFirstUnique(const Container& c) {
using T = typename Container::value_type;
std::unordered_map<T, int> counts;
for (const T& x : c) ++counts[x];
for (const T& x : c) if (counts[x] == 1) return x;
return std::nullopt;
}
// Для случая "все дубликаты, кроме одного" — чистый один проход (XOR)
int findUniqueSinglePass(const std::vector<int>& v) {
int result = 0;
for (int x : v) result ^= x;
return result;
}
int main() {
assert(findFirstUnique(std::vector<int>{1,2,1,3,2}) == 3);
assert(findFirstUnique(std::string("aabbcd")) == 'c');
assert(!findFirstUnique(std::vector<int>{1,1,2,2}));
assert(findUniqueSinglePass({4,1,2,1,2}) == 4);
}Ключевые моменты
- "Один проход" на собеседовании обычно означает O(n) с постоянным числом итераций по данным.
- Для целых с гарантией "один уникальный, все остальные дважды" — XOR за истинный один проход.
std::optional— идиоматичный возврат "нет результата" в C++17.- Для строк первый неповторяющийся символ: тот же подход с
std::array<int, 256>счётчиком.
Оглавление
