JuniorКодЧастоЕщё не отвечали
Найдите элементы двух массивов, которые попадаются только в каждом из них. Используйте STL.
Даны два массива целых чисел. Верните элементы, которые встречаются ровно в одном из них (симметрическая разность). Используйте STL.
Требования:
- Решайте через алгоритмы стандартной библиотеки, а не ручной цикл сравнения.
- Возвращаемые значения уникальны в смысле принадлежности множеству.
#include <vector>
std::vector<int> symmetricDifference(std::vector<int> a, std::vector<int> b) {
// ваш код здесь
}Допишите реализацию.
Отсортируйте оба массива, затем используйте std::set_symmetric_difference для получения элементов, присутствующих ровно в одном из двух массивов. Альтернатива — вставить один массив в unordered_set и проверять второй — O(n+m) в среднем при O(n) дополнительной памяти.
- ✗Забывать, что
std::set_symmetric_differenceтребует отсортированного входа - ✗Не использовать
std::back_inserterкак выходной итератор - ✗Путать симметрическую разность (ровно в одном) с разностью (в первом, но не во втором)
- →Какова временная сложность
std::set_symmetric_difference? - →Как найти пересечение двух массивов с помощью STL?
Оглавление
Задача
Найдите элементы, которые присутствуют только в одном из двух массивов (симметрическая разность).
Решение
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <cassert>
// Подход 1: STL set_symmetric_difference — O((n+m) log(n+m))
std::vector<int> symmDiffSTL(std::vector<int> a, std::vector<int> b) {
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
std::vector<int> result;
std::set_symmetric_difference(
a.begin(), a.end(),
b.begin(), b.end(),
std::back_inserter(result));
return result;
}
// Подход 2: unordered_set — O(n+m) среднее, O(n+m) память
std::vector<int> symmDiffHash(const std::vector<int>& a, const std::vector<int>& b) {
std::unordered_set<int> setA(a.begin(), a.end());
std::unordered_set<int> setB(b.begin(), b.end());
std::vector<int> result;
for (int x : a) if (!setB.count(x)) result.push_back(x);
for (int x : b) if (!setA.count(x)) result.push_back(x);
return result;
}
int main() {
std::vector<int> a = {1, 2, 3, 4};
std::vector<int> b = {3, 4, 5, 6};
auto r1 = symmDiffSTL(a, b);
assert(r1 == std::vector<int>({1, 2, 5, 6})); // отсортировано
auto r2 = symmDiffHash(a, b);
std::sort(r2.begin(), r2.end());
assert(r2 == std::vector<int>({1, 2, 5, 6}));
}Ключевые моменты
std::set_symmetric_difference— декларативный, читаемый, но требует сортировки.unordered_setвариант — быстрее на больших данных (O(n+m) vs O((n+m) log)).- Оба подхода обрабатывают дубликаты одинаково (игнорируют их).
Оглавление
