SeniorКодИногдаЕщё не отвечали
Сложить два разреженных вектора из сортированных пар (индекс, значение)
Два разреженных вектора заданы списками пар (индекс, значение), отсортированных по индексу. Верните их сумму в той же разреженной форме, отсортированную, выбросив записи с нулевой суммой.
Требования:
- Merge двумя указателями за O(|l| + |r|).
- Используйте широкий аккумулятор против переполнения при сложении.
struct TItem { int Idx; long long Val; };
std::vector<TItem> sumSparse(const std::vector<TItem>& l, const std::vector<TItem>& r) {
// ваш код здесь
}Допишите реализацию.
Merge двумя указателями по отсортированным спискам: при равных индексах складываем значения, иначе выводим меньший индекс и двигаем тот указатель. Пропускаем записи с нулевой суммой (они уже не ненулевые). Линейно по суммарной длине, O(|l|+|r|).
- ✗Забыть выбросить записи с нулевой суммой значений
- ✗Двигать оба указателя, когда совпал лишь один индекс
- ✗Накапливать в узком типе и переполняться при сложении двух больших значений
- →Чем это отличается от скалярного произведения разреженных векторов, где умножают?
- →Почему нулевую сумму нужно удалять, чтобы остаться по-настоящему разреженным?
Оглавление
Задача
Сложите два разреженных вектора (индекс, значение) merge'ом двумя указателями за O(|l|+|r|).
Решение
#include <vector>
struct TItem { int Idx; long long Val; };
std::vector<TItem> sumSparse(const std::vector<TItem>& l, const std::vector<TItem>& r) {
std::vector<TItem> out;
size_t i = 0, j = 0;
while (i < l.size() || j < r.size()) {
if (j >= r.size() || (i < l.size() && l[i].Idx < r[j].Idx)) {
out.push_back(l[i++]);
} else if (i >= l.size() || r[j].Idx < l[i].Idx) {
out.push_back(r[j++]);
} else { // равные индексы
long long sum = l[i].Val + r[j].Val;
if (sum != 0) out.push_back({l[i].Idx, sum});
++i; ++j;
}
}
return out;
}Ключевые моменты
- Merge двумя указателями: складываем при равных индексах, иначе берём меньший.
- Нулевые суммы выкидываем — иначе вектор перестаёт быть разреженным.
- Аккумулятор широкий, чтобы не переполниться.
Оглавление
