📝 Слияние отсортированных массивов с суммированием значений

leetcoder, 02-03-2025 ,

405

Ссылка на задачу - 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