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

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

Эта задача требует эффективного объединения двух отсортированных массивов с сложностью O(n + m) с использованием техники двух указателей.

Подход: Техника двух указателей

Идея простая:

1. Создаем новый массив размером n + m
2. Используем два указателя для обхода обоих массивов
3. На каждом шаге сравниваем элементы и добавляем меньший в результат
4. Добавляем оставшиеся элементы

Решение

public class MergeSortedArrays {
    public static int[] mergeArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return nums1 == null ? nums2 : nums1;
        }
        
        int n = nums1.length;
        int m = nums2.length;
        int[] result = new int[n + m];
        
        int i = 0;  // указатель на nums1
        int j = 0;  // указатель на nums2
        int k = 0;  // указатель на result
        
        // Сравниваем элементы обоих массивов
        while (i < n && j < m) {
            if (nums1[i] <= nums2[j]) {
                result[k++] = nums1[i++];
            } else {
                result[k++] = nums2[j++];
            }
        }
        
        // Добавляем оставшиеся элементы из nums1
        while (i < n) {
            result[k++] = nums1[i++];
        }
        
        // Добавляем оставшиеся элементы из nums2
        while (j < m) {
            result[k++] = nums2[j++];
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        // Пример 1
        int[] nums1 = {1, 2, 3};
        int[] nums2 = {2, 5, 6};
        int[] result1 = mergeArrays(nums1, nums2);
        System.out.println(Arrays.toString(result1));
        // Вывод: [1, 2, 2, 3, 5, 6]
        
        // Пример 2
        int[] nums3 = {1};
        int[] nums4 = {};
        int[] result2 = mergeArrays(nums3, nums4);
        System.out.println(Arrays.toString(result2));
        // Вывод: [1]
        
        // Пример 3
        int[] nums5 = {};
        int[] nums6 = {1, 2, 3};
        int[] result3 = mergeArrays(nums5, nums6);
        System.out.println(Arrays.toString(result3));
        // Вывод: [1, 2, 3]
        
        // Пример 4
        int[] nums7 = {1, 3, 5, 7};
        int[] nums8 = {2, 4, 6, 8};
        int[] result4 = mergeArrays(nums7, nums8);
        System.out.println(Arrays.toString(result4));
        // Вывод: [1, 2, 3, 4, 5, 6, 7, 8]
    }
}

Пошаговый пример работы

nums1 = [1, 2, 3], nums2 = [2, 5, 6]

Шаг 0:
I: 1  J: 2  K: 0
[_,_,_,_,_,_]

Шаг 1: nums1[0]=1 < nums2[0]=2 → результат[0]=1
I: 1  J: 0  K: 1
[1,_,_,_,_,_]

Шаг 2: nums1[1]=2 <= nums2[0]=2 → результат[1]=2
I: 2  J: 0  K: 2
[1,2,_,_,_,_]

Шаг 3: nums1[2]=3 > nums2[0]=2 → результат[2]=2
I: 2  J: 1  K: 3
[1,2,2,_,_,_]

Шаг 4: nums1[2]=3 < nums2[1]=5 → результат[3]=3
I: 3  J: 1  K: 4
[1,2,2,3,_,_]

Шаг 5: i >= n, добавляем остаток nums2
[1,2,2,3,5,6]

Оптимизация с использованием System.arraycopy()

public class MergeSortedArraysOptimized {
    public static int[] mergeArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0) return nums2;
        if (nums2 == null || nums2.length == 0) return nums1;
        
        int n = nums1.length;
        int m = nums2.length;
        int[] result = new int[n + m];
        
        int i = 0, j = 0, k = 0;
        
        while (i < n && j < m) {
            if (nums1[i] <= nums2[j]) {
                result[k++] = nums1[i++];
            } else {
                result[k++] = nums2[j++];
            }
        }
        
        // Копируем оставшиеся элементы в один вызов
        if (i < n) {
            System.arraycopy(nums1, i, result, k, n - i);
        }
        if (j < m) {
            System.arraycopy(nums2, j, result, k, m - j);
        }
        
        return result;
    }
}

Альтернатива с использованием Collections

import java.util.*;

public class MergeSortedArraysSimple {
    public static int[] mergeArrays(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        
        list.addAll(Arrays.stream(nums1).boxed().collect(Collectors.toList()));
        list.addAll(Arrays.stream(nums2).boxed().collect(Collectors.toList()));
        
        Collections.sort(list);
        
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
    
    // ИЛИ более простой вариант
    public static int[] mergeArraysSimpler(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length + nums2.length];
        System.arraycopy(nums1, 0, result, 0, nums1.length);
        System.arraycopy(nums2, 0, result, nums1.length, nums2.length);
        Arrays.sort(result);
        return result;
    }
}

Однако эти варианты имеют сложность O((n+m)log(n+m)) из-за сортировки!

Тесты

public class MergeSortedArraysTest {
    private MergeSortedArrays merger = new MergeSortedArrays();
    
    @Test
    public void testExample1() {
        int[] nums1 = {1, 2, 3};
        int[] nums2 = {2, 5, 6};
        int[] expected = {1, 2, 2, 3, 5, 6};
        int[] result = merger.mergeArrays(nums1, nums2);
        assertArrayEquals(expected, result);
    }
    
    @Test
    public void testExample2() {
        int[] nums1 = {1};
        int[] nums2 = {};
        int[] expected = {1};
        int[] result = merger.mergeArrays(nums1, nums2);
        assertArrayEquals(expected, result);
    }
    
    @Test
    public void testEmptyArrays() {
        int[] nums1 = {};
        int[] nums2 = {};
        int[] expected = {};
        int[] result = merger.mergeArrays(nums1, nums2);
        assertArrayEquals(expected, result);
    }
    
    @Test
    public void testFirstArrayEmpty() {
        int[] nums1 = {};
        int[] nums2 = {1, 2, 3};
        int[] expected = {1, 2, 3};
        int[] result = merger.mergeArrays(nums1, nums2);
        assertArrayEquals(expected, result);
    }
    
    @Test
    public void testDuplicates() {
        int[] nums1 = {1, 1, 1};
        int[] nums2 = {1, 1, 1};
        int[] expected = {1, 1, 1, 1, 1, 1};
        int[] result = merger.mergeArrays(nums1, nums2);
        assertArrayEquals(expected, result);
    }
    
    @Test
    public void testNegativeNumbers() {
        int[] nums1 = {-5, -2, 0, 3};
        int[] nums2 = {-3, 1, 4};
        int[] expected = {-5, -3, -2, 0, 1, 3, 4};
        int[] result = merger.mergeArrays(nums1, nums2);
        assertArrayEquals(expected, result);
    }
}

Анализ сложности

• Временная сложность: O(n + m) — проходим через каждый элемент один раз
• Пространственная сложность: O(n + m) — нужен новый массив для результата

Визуализация алгоритма

аррей1: [1, 2, 3]
         ↑ указатель i
аррей2: [2, 5, 6]
         ↑ указатель j
результат: [_,_,_,_,_,_]
           ↑ указатель k

Сравниваем nums1[i] с nums2[j]:
- если nums1[i] ≤ nums2[j], копируем nums1[i] в result[k] и увеличиваем i
- иначе копируем nums2[j] в result[k] и увеличиваем j
- в любом случае увеличиваем k

Когда один из массивов закончился:
- копируем оставшиеся элементы из другого массива

Ключевые моменты

• Техника двух указателей — эффективный способ работы с двумя отсортированными структурами
• O(n + m) сложность — оптимальна, так как нужно обработать все элементы
• Стабильность — алгоритм сохраняет относительный порядок равных элементов
• Edge cases — обрабатываем пустые массивы и массивы разного размера