Объединение отсортированных массивов

Даны два целочисленных массива nums1 и nums2, отсортированных в возрастающем порядке, и два целых числа m и n, представляющие количество элементов в nums1 и nums2 соответственно.

Объедините nums1 и nums2 в один массив, отсортированный в возрастающем порядке.

Функция не должна ничего возвращать, вместо этого нужно мутировать массив nums1. Для этого, nums1 имеет длину m + n, где первые m элементов обозначают элементы, которые должны быть объединены, а последние n элементов установлены в 0 и должны быть проигнорированы. nums2 имеет длину n.

Задача со звездочкой: Сможете придумать алгоритм, который работает за время O(m + n)?

Пример №1

Ввод: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Вывод: [1,2,2,3,5,6]
Объяснение: Массивы, которые мы объединяем, - [1,2,3] и [2,5,6].
Результат объединения - [1,2,2,3,5,6].

Пример №2

Ввод: nums1 = [1], m = 1, nums2 = [], n = 0
Вывод: [1]
Объяснение: Массивы, которые мы объединяем, - [1] и [].
Результат объединения - [1].

Пример №3

Ввод: nums1 = [0], m = 0, nums2 = [1], n = 1
Вывод: [1]
Объяснение: Массивы, которые мы объединяем, - [] и [1].
Результат объединения - [1].
Обратите внимание, что так как m = 0, в nums1 нет элементов. 0 здесь только для того, чтобы гарантировать, что результат слияния может поместиться в nums1.

Решение

Одним из наиболее частых подходов к решению этой задачи является использование двух указателей.

Начинаем перебор с конца каждого из массивов и сравниваем элементы. Больший элемент помещается в конец массива nums1. Если элементы равны, мы можем поместить любой из них, так как массивы отсортированы в возрастающем порядке. Продолжаем этот процесс, пока не пройдем через все элементы в nums2.

Обратите внимание, что если элементы в nums1 закончились, мы должны скопировать оставшиеся элементы из nums2.

• Это решение требует O(m + n) времени, так как каждый элемент обоих массивов проверяется максимум один раз.

Код решения в виде текста

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Нужно модифицировать nums1.
 */
const merge = (nums1, m, nums2, n) => {
  // Инициализация трех указателей: i указывает на конец nums1,
  // nums2Pointer указывает на конец nums2,
  // lastFreeCell указывает на последнюю позицию в массиве nums1,
  // куда можно записать значение.
  let nums1Pointer = m - 1
  let nums2Pointer = n - 1
  let lastFreeCell = m + n - 1

  // Проходим по массивам с конца,
  // пока не обработаем все элементы в nums1 и nums2.
  while (nums1Pointer >= 0 && nums2Pointer >= 0) {
    // Если элемент nums2 больше элемента nums1,
    // помещаем его в текущую позицию lastFreeCell в nums1.
    if (nums1[nums1Pointer] < nums2[nums2Pointer]) {
      nums1[lastFreeCell] = nums2[nums2Pointer]
      // Перемещаем указатель nums2Pointer на следующий элемент nums2.
      nums2Pointer--
    } else {
      // Если элемент nums1 больше или равен элементу nums2,
      // помещаем его в текущую позицию lastFreeCell в nums1.
      nums1[lastFreeCell] = nums1[nums1Pointer]
      // Перемещаем указатель nums1Pointer на следующий элемент nums1.
      nums1Pointer--
    }
    // Перемещаем указатель lastFreeCell на следующую позицию в nums1.
    lastFreeCell--
  }

  // Если все элементы nums1 были обработаны,
  // но остались элементы в nums2, копируем их в nums1.
  while (nums2Pointer >= 0) {
    nums1[lastFreeCell] = nums2[nums2Pointer]
    lastFreeCell--
    nums2Pointer--
  }
};

Больше интересных разборов в канале @js_is_easy, подписывайся