MiddleКодЧастоЕщё не отвечали
Элементы одного сортированного списка, которых нет в другом
Даны две неубывающие последовательности целых. Верните все элементы первой, которых НЕТ во второй. filter([1,2,3], [3,4]) → [1,2]; filter([1,2,2], [2]) → [1].
Требования:
- O(n + m) по времени, O(1) доп. памяти кроме вывода — merge двумя указателями, без бинпоиска.
std::vector<int> filterSorted(const std::vector<int>& a, const std::vector<int>& b) {
// ваш код здесь
}Допишите реализацию.
Merge двумя указателями: при a[i] < b[j] элемент a[i] отсутствует в b, выводим его и двигаем i. При a[i] == b[j] пропускаем a[i] (он есть). При a[i] > b[j] двигаем j. После исчерпания b выводим остаток a. O(n + m), O(1).
- ✗Неверная обработка дублей, напр. удаление обеих копий значения, которое в b лишь раз
- ✗Забыть вывести хвост a после исчерпания b
- ✗Не сдвигать указатель при равенстве, вызывая бесконечный цикл
- →Как меняется обработка дублей, если в b могут быть повторы?
- →Почему merge двумя указателями предпочтительнее хеш-множества, когда оба входа уже отсортированы?
Оглавление
Задача
Верните элементы первого сортированного списка, отсутствующие во втором, merge'ом за O(n + m).
Решение
#include <vector>
std::vector<int> filterSorted(const std::vector<int>& a, const std::vector<int>& b) {
std::vector<int> out;
size_t i = 0, j = 0;
while (i < a.size()) {
if (j >= b.size() || a[i] < b[j]) out.push_back(a[i++]); // нет в b
else if (a[i] == b[j]) ++i; // есть в b
else ++j; // a[i] > b[j]
}
return out;
}Ключевые моменты
- Сравнение голов решает: вывести, пропустить или сдвинуть
j. - При равенстве сдвигаем только
i— иначе теряем дубли или зависаем. - O(n + m), без хеширования и бинпоиска.
Оглавление
