Урок по Java
Java-файл

Введение

Проблема нахождения медианы двух отсортированных массивов — это классический вопрос на собеседовании по программированию. Задача состоит в том, чтобы эффективно найти медиану с временной сложностью O(log(min(m, n))), где m и n — размеры двух массивов. В этой статье мы рассмотрим решение Java, которое использует двоичный поиск для достижения такой эффективности.

Постановка задачи

Дано два отсортированных массива nums1 и nums2. Найдите медиану этих двух отсортированных массивов. Общая сложность времени выполнения должна составлять O(log(min(m, n))), где m и n — размеры двух массивов.

Подход

Чтобы решить эту проблему, мы используем метод двоичного поиска в меньшем из двух массивов. Цель состоит в том, чтобы разделить оба массива так, чтобы левая половина содержала все элементы, меньшие или равные элементам в правой половине. Вот пошаговое объяснение:

1. Убедитесь, что nums1 — это меньший массив.: для упрощения двоичного поиска убедитесь, что nums1 — это меньший массив.
2. Выполнить двоичный поиск: используйте двоичный поиск по nums1, чтобы найти правильный раздел.
3. Разделение: разделите оба массива так, чтобы левая часть содержала младшие элементы, а правая — верхние элементы.
4. Вычислить медиану: на основе разделов вычислить медиану.

Решение

Вот подробная реализация решения на Java:

public class MedianOfTwoSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int x = nums1.length;
        int y = nums2.length;
        int low = 0, high = x;

        while (low  minY) {
                high = partitionX - 1;
            } else {
                low = partitionX   1;
            }
        }

        throw new IllegalArgumentException("Input arrays are not sorted");
    }

    public static void main(String[] args) {
        MedianOfTwoSortedArrays solution = new MedianOfTwoSortedArrays();

        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println("Median: "   solution.findMedianSortedArrays(nums1, nums2)); // Output: 2.0

        int[] nums1_2 = {1, 2};
        int[] nums2_2 = {3, 4};
        System.out.println("Median: "   solution.findMedianSortedArrays(nums1_2, nums2_2)); // Output: 2.5
    }
}

Объяснение

1. Инициализация: убедитесь, что nums1 — это меньший массив.
2. Двоичный поиск: выполните двоичный поиск по номеру nums1, чтобы найти правильный раздел.
3. Разбиение и расчет медианы: вычислите максимум левых элементов и минимум правых элементов, чтобы найти медиану.

Заключение

Этот подход двоичного поиска обеспечивает эффективное решение для поиска медианы двух отсортированных массивов. Используя бинарный поиск в меньшем массиве, решение достигает временной сложности O(log(min(m, n))), что делает его подходящим для больших входных массивов.