Ссылка на задачу - 2570. Merge Two 2D Arrays by Summing Values.
📌 Описание задачи
Даны два отсортированных списка nums1 и nums2, где каждый элемент представлен в виде [id, value].
Нужно объединить их в один список, упорядоченный по id, при этом суммируя значения для совпадающих id.
💡 Идея
Так как оба списка уже отсортированы по id, можно пройтись по ним одновременно, сравнивая id и добавляя элементы в результат.
Такой метод позволяет решить задачу за O(n + m) без дополнительной сортировки.
🛠 Подробности подхода
- Используем два индекса
i и j для итерации по nums1 и nums2.
- Сравниваем текущие
id:
- Если
id1 < id2 → добавляем nums1[i] в результат, сдвигаем i.
- Если
id1 > id2 → добавляем nums2[j] в результат, сдвигаем j.
- Если
id1 == id2 → суммируем значения, добавляем результат, сдвигаем оба указателя.
- Добавляем оставшиеся элементы из
nums1 и nums2, если таковые имеются.
⏳ Асимптотика
- Время:
O(n + m) – один проход по обоим массивам.
- Память:
O(n + m) – для хранения результирующего массива.
📜 Исходный код
use std::cmp::Ordering;
impl Solution {
pub fn merge_arrays(nums1: Vec<Vec<i32>>, nums2: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut result = Vec::new();
let (mut i, mut j) = (0, 0);
// Merge both arrays while iterating through them
while i < nums1.len() && j < nums2.len() {
let (id1, val1) = (nums1[i][0], nums1[i][1]);
let (id2, val2) = (nums2[j][0], nums2[j][1]);
match id1.cmp(&id2) {
Ordering::Less => {
result.push(vec![id1, val1]);
i += 1;
}
Ordering::Greater => {
result.push(vec![id2, val2]);
j += 1;
}
Ordering::Equal => {
result.push(vec![id1, val1 + val2]);
i += 1;
j += 1;
}
}
}
// Append remaining elements efficiently
result.extend_from_slice(&nums1[i..]);
result.extend_from_slice(&nums2[j..]);
result
}
}
Tags: #rust #algorithms