Условие задачи "на пальцах"
Представьте ситуацию:
У вас есть две колоды карт, и в каждой колоде карты уже отсортированы по возрастанию:
Колода 1: [1, 3, 5, 7] 🃏
Колода 2: [2, 4, 6] 🃏
Ваша задача: объединить эти две колоды в одну, чтобы все карты остались отсортированными:
Результат: [1, 2, 3, 4, 5, 6, 7] ✅
Формальное условие:
Даны два отсортированных массива:
- nums1 — массив длиной m + n, где первые m элементов — это отсортированные числа, а последние n элементов = 0 (пустые места для заполнения)
- nums2 — массив длиной n с отсортированными числами
Нужно: объединить nums2 в nums1 так, чтобы nums1 стал одним отсортированным массивом длиной m + n.
⚠️ Важно: Результат должен быть записан внутри массива nums1, а не возвращён как новый массив!
Пример:
Вход:
nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6], n = 3
Выход: nums1 = [1, 2, 2, 3, 5, 6]
🔵🔴🔴🔵🔴🔴 (🔵 из nums1, 🔴 из nums2)
Как думать о решении?
Простая аналогия: "Слияние двух очередей" 🚶
Представьте, что у вас есть две очереди людей по росту:
Очередь 1: [150см, 160см, 170см, _, _, _] (3 человека + 3 пустых места)
Очередь 2: [155см, 165см, 175см] (3 человека)
Вам нужно перестроить всех в одну очередь по росту, используя пустые места в первой очереди.
Два подхода:
❌ Подход 1: С начала (неоптимальный)
Берём наименьшие элементы с начала обоих массивов и записываем в новый массив.
Проблема: Нужно создавать новый массив или сдвигать элементы в nums1, что медленно! 🐌
✅ Подход 2: С конца (оптимальный!)
Заполняем nums1 с конца, сравнивая наибольшие элементы обоих массивов.
Преимущество: Не нужно сдвигать элементы — сразу пишем на свободные места!
Решение на Java с комментариями
Заключение
Пример, рассмотренный в статье, можно найти по адресу:
https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task88_mergeSortedArray/Solution.java