Нахождение медианы двух отсортированных массивов — распространенная проблема в программировании и алгоритмических собеседованиях. В этой статье мы рассмотрим несколько методов решения этой проблемы с использованием разговорного языка и приведем примеры кода. Итак, приступим!

Метод 1: объединение и сортировка

Один простой подход — объединить оба массива в один отсортированный массив, а затем найти медиану. Вот пример на Python:

def find_median(nums1, nums2):
    merged = nums1 + nums2
    merged.sort()
    n = len(merged)
    if n % 2 == 0:
        return (merged[n // 2 - 1] + merged[n // 2]) / 2
    else:
        return merged[n // 2]

Метод 2: два указателя

Другой подход — использовать два указателя для одновременного перемещения по обоим массивам. Мы сравниваем элементы по текущим указателям и соответственно перемещаем указатели. Этот метод позволяет избежать необходимости объединения массивов:

def find_median(nums1, nums2):
    total_len = len(nums1) + len(nums2)
    mid = total_len // 2
    i, j = 0, 0
    merged = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            merged.append(nums1[i])
            i += 1
        else:
            merged.append(nums2[j])
            j += 1
    # Add the remaining elements from nums1 or nums2
    merged.extend(nums1[i:])
    merged.extend(nums2[j:])
    if total_len % 2 == 0:
        return (merged[mid - 1] + merged[mid]) / 2
    else:
        return merged[mid]

Метод 3: двоичный поиск

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

def find_median(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    n1, n2 = len(nums1), len(nums2)
    low, high = 0, n1
    while low <= high:
        partition1 = (low + high) // 2
        partition2 = (n1 + n2 + 1) // 2 - partition1
        maxLeft1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
        minRight1 = float('inf') if partition1 == n1 else nums1[partition1]
        maxLeft2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
        minRight2 = float('inf') if partition2 == n2 else nums2[partition2]
        if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
            if (n1 + n2) % 2 == 0:
                return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2
            else:
                return max(maxLeft1, maxLeft2)
        elif maxLeft1 > minRight2:
            high = partition1 - 1
        else:
            low = partition1 + 1

В этой статье мы рассмотрели три метода поиска медианы двух отсортированных массивов: слияние и сортировка, два указателя и двоичный поиск. У каждого метода есть свои плюсы и минусы, и выбор зависит от конкретных требований вашей задачи. Реализовав эти алгоритмы на Python, вы сможете уверенно решить проблему «медианы двух отсортированных массивов». Приятного кодирования!