88. Merge Sorted Array

Задача

Даны два отсортированных массива nums1 и nums2 (с длинами m и n). Слейте их в nums1 in-place в отсортированном порядке.

Примеры

Пример 1

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Пояснение

Сливаем [1,2,3] и [2,5,6], результат [1,2,2,3,5,6].

Пример 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Пояснение

Сливаем [1] и [], результат [1].

Пример 3

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]

Пояснение

Сливаем [] и [1], результат [1]. m = 0, поэтому в nums1 нет своих элементов; 0 нужен лишь для размера.

Решение

Решение

// Временная сложность: O(m + n)
//   В худшем случае мы обрабатываем все m элементов из nums1 и все n элементов из nums2
//   Основной цикл while выполняется максимум m + n итераций
// Пространственная сложность: O(1)
 
var merge = function(nums1, m, nums2, n) {
    // Инициализируем три указателя
    let nums1Index = m - 1; // Указатель на последний реальный элемент в nums1
    let nums2Index = n - 1; // Указатель на последний элемент в nums2
    let writePosition = m + n - 1; // Указатель на последнюю позицию в итоговом массиве
 
    // Продолжаем пока в nums2 есть необработанные элементы
    while (nums2Index >= 0) {
        // Сравниваем элементы с конца обоих массивов
        // Проверяем что nums1Index >= 0 (элементы nums1 не закончились)
        // И что текущий элемент nums1 больше текущего элемента nums2
        if (nums1Index >= 0 && nums1[nums1Index] > nums2[nums2Index]) {
            // Если элемент из nums1 больше - помещаем его в конец
            nums1[writePosition] = nums1[nums1Index];
            nums1Index--; // Сдвигаем указатель nums1 влево
        } else {
            // Иначе берём элемент из nums2 (он больше или равен, либо nums1 закончился)
            nums1[writePosition] = nums2[nums2Index];
            nums2Index--; // Сдвигаем указатель nums2 влево
        }
 
        // Сдвигаем указатель позиции записи влево
        writePosition--;
    }
 
    // Когда nums2Index < 0, все элементы nums2 обработаны
    // Оставшиеся элементы nums1 (если есть) уже на своих местах
};
 
// nums1 = [1,2,3,0,0,0], m = 3
// nums2 = [2,5,6], n = 3
 
// Шаг 1: 6 > 3 → [1,2,3,0,0,6]
// Шаг 2: 5 > 3 → [1,2,3,0,5,6]
// Шаг 3: 3 > 2 → [1,2,3,3,5,6]
// Шаг 4: 2 = 2 → [1,2,2,3,5,6]
// Шаг 5: 2 > 1 → [1,2,2,3,5,6]
// Результат: [1,2,2,3,5,6]