JuniorКодЧастоЕщё не отвечали
Индекс первого неповторяющегося символа
Дана строка. Верните индекс первого символа, встречающегося ровно один раз. Если такого символа нет, верните -1.
Требования:
O(n²) «считать каждый символ повторным сканированием».
- Два прохода по строке с таблицей частот — нормально; избегайте подхода
int firstUniqueChar(const std::string& s) {
// ваш код здесь
}Допишите реализацию.
Первый проход: посчитайте вхождения каждого символа в хеш-таблице (или массиве фиксированного размера для известного алфавита). Второй проход: идите по строке слева направо и верните индекс первого символа со счётчиком 1. Верните -1, если такого нет. O(n) время.
- ✗Повторно сканировать строку на каждый символ, вырождаясь в O(n²)
- ✗Возвращать первую запись со счётчиком 1 из неупорядоченной таблицы, теряя исходный порядок
- ✗Путать «ещё не встречался» с «встречается ровно один раз»
- →Почему второй проход должен идти по строке, а не по таблице?
- →Как сделать это за один проход, если хранить ещё и индекс каждого символа?
Оглавление
Задача
Верните индекс первого символа, встречающегося ровно один раз; иначе -1. За O(n).
Решение
#include <string>
#include <unordered_map>
int firstUniqueChar(const std::string& s) {
std::unordered_map<char, int> count;
for (char c : s) ++count[c]; // первый проход: частоты
for (int i = 0; i < static_cast<int>(s.size()); ++i)
if (count[s[i]] == 1) return i; // второй проход: по строке
return -1;
}Ключевые моменты
- Второй проход идёт по строке, а не по таблице, чтобы сохранить исходный порядок.
- «Первый со счётчиком 1» — не то же, что «первый ещё не виденный».
- Два прохода дают O(n); повторный скан на символ был бы O(n²).
Оглавление
