MiddleКодИногдаЕщё не отвечали
Общие элементы в каждом K-префиксе двух массивов за O(N)
Даны два массива целых длины N. Для каждого K от 1 до N выведите количество различных значений, встречающихся в ОБОИХ префиксах длины K. Дубли внутри массива считаются один раз. Пример: {1,2,3} и {2,1,3,1} → {0,1,2,3}.
Требования:
- O(N) суммарно.
std::vector<int> commonInPrefixes(const std::vector<int>& a, const std::vector<int>& b) {
// ваш код здесь
}Допишите реализацию.
Идите по обоим префиксам синхронно с двумя хеш-множествами seenA, seenB и счётчиком common. Новое значение из a уже есть в seenB — увеличьте common; так же для нового b в seenA. Записывайте common после каждого шага. Один проход, O(N).
- ✗Перестраивать префиксные множества на каждом K вместо инкрементального расширения
- ✗Считать дублирующееся значение новым совпадением более одного раза
- ✗Забыть, что новый элемент проверяется против множества ДРУГОГО массива
- →Как меняется ответ, если пересечение учитывает кратность (минимум частот)?
- →Почему счётчик остаётся верным, когда оба префикса растут вместе?
Оглавление
Задача
Для каждого K от 1 до N посчитайте общие различные значения в префиксах длины K обоих массивов.
Решение
#include <vector>
#include <unordered_set>
std::vector<int> commonInPrefixes(const std::vector<int>& a, const std::vector<int>& b) {
std::unordered_set<int> seenA, seenB;
std::vector<int> result;
int common = 0;
for (size_t k = 0; k < a.size(); ++k) {
if (seenA.insert(a[k]).second && seenB.count(a[k])) ++common;
if (seenB.insert(b[k]).second && seenA.count(b[k])) ++common;
result.push_back(common);
}
return result;
}Ключевые моменты
- Два множества и счётчик
commonрастут вместе с префиксами. - Новый элемент проверяется против множества другого массива — отсюда O(N).
insert(...).secondотсекает дубли внутри одного массива.
Оглавление
