Нахождение медианы двух отсортированных массивов

Решение

Понимание задачи

Найти медиану двух отсортированных массивов. Медиана — среднее значение в объединённом отсортированном массиве.

Простое решение: Объединение и сортировка

def find_median(nums1, nums2):
    merged = sorted(nums1 + nums2)
    n = len(merged)
    if n % 2 == 1:
        return float(merged[n // 2])
    else:
        return (merged[n // 2 - 1] + merged[n // 2]) / 2.0

Примеры:

• [1, 3] и [2] -> [1, 2, 3] -> медиана 2.0
• [1, 2] и [3, 4] -> [1, 2, 3, 4] -> медиана (2+3)/2 = 2.5

Сложность

• Временная: O((m+n) log (m+n))
• Пространственная: O(m+n)

Оптимальное решение: Двухуказатель

def find_median_optimal(nums1, nums2):
    m, n = len(nums1), len(nums2)
    total = m + n
    is_odd = total % 2 == 1
    
    median1, median2 = None, None
    i, j = 0, 0
    
    # Проходим до середины
    for _ in range(total // 2 + 1):
        median2 = median1
        
        if i < m and (j >= n or nums1[i] <= nums2[j]):
            median1 = nums1[i]
            i += 1
        else:
            median1 = nums2[j]
            j += 1
    
    if is_odd:
        return float(median1)
    else:
        return (median1 + median2) / 2.0

Сложность: O(m+n) время, O(1) дополнительная память.

Тестирование

assert find_median([1, 3], [2]) == 2.0
assert find_median([1, 2], [3, 4]) == 2.5
assert find_median([], [1, 2, 3]) == 2.0
assert find_median([1], [2]) == 1.5
assert find_median([1, 2, 3], [4, 5, 6]) == 3.5

Алгоритм двухуказателя

1. Используем два указателя i и j для массивов nums1 и nums2
2. Сравниваем элементы и выбираем меньший
3. Проходим до середины объединённого массива
4. Для нечётного: медиана — последний элемент
5. Для чётного: медиана — среднее последних двух элементов

Граничные случаи

• Пустой массив: find_median([], [1, 2, 3]) = 2.0
• Одноэлементные: find_median([1], [2]) = 1.5
• Разные размеры: find_median([1], [2, 3, 4, 5]) = 3.0
• Дублирующиеся: find_median([1, 1], [1, 1]) = 1.0

Выводы

• Двухуказатель — оптимальное решение O(m+n) время
• Объединение — простое, но O(n log n)
• Ключевая идея: слияние двух отсортированных массивов
• Для QA: проверить все граничные случаи и разные размеры