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

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

Условие задачи:
Даны два отсортированных массива nums1 и nums2. Необходимо объединить их в один отсортированный массив.

Использовать встроенную сортировку нельзя.

Код:

public int[] mergeSortedArrays(int[] nums1, int[] nums2) {
    // код тут
}

Примеры:

[1, 3, 5] и [2, 4, 6] → [1, 2, 3, 4, 5, 6]

[1, 2, 7] и [3, 4, 5] → [1, 2, 3, 4, 5, 7]

[] и [1, 2, 3] → [1, 2, 3]

Спойлеры к решению

Подсказки

💡 Используй отдельный указатель для каждого входного массива.
💡 Сравнивай текущие элементы и записывай меньший в результат.
💡 После добавления элемента передвигай соответствующий указатель.
💡 Когда один массив закончится, скопируй остаток второго.

Решение

public int[] mergeSortedArrays(int[] nums1, int[] nums2) {
    int[] result = new int[nums1.length + nums2.length];

    int firstIndex = 0;
    int secondIndex = 0;
    int resultIndex = 0;

    while (firstIndex < nums1.length
            && secondIndex < nums2.length) {

        if (nums1[firstIndex] <= nums2[secondIndex]) {
            result[resultIndex++] = nums1[firstIndex++];
        } else {
            result[resultIndex++] = nums2[secondIndex++];
        }
    }

    while (firstIndex < nums1.length) {
        result[resultIndex++] = nums1[firstIndex++];
    }

    while (secondIndex < nums2.length) {
        result[resultIndex++] = nums2[secondIndex++];
    }

    return result;
}

Каждый элемент обоих массивов обрабатывается ровно один раз. Повторяющиеся значения сохраняются.

Временная сложность — O(n + m), дополнительная память — O(n + m) для результирующего массива.