Пример решения задачи #4. Python LeetCode, Медиана двух отсортированных массивов

Вариант решения задачи на языке программирования Python с LeetCode.
Категория: Алгоритмы.
Название задачи: Медиана двух отсортированных массивов
Сложность: Hard.
Статус решения: "Решено".

Условие задачи:
Даны два отсортированных массива nums1 и nums2 соответственно размерами m и n. Необходимо найти медиану объединенного массива. Общая временная сложность алгоритма должна быть O(log(m+n)).

Решение:

Python

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        Поиск медианы двух отсортированных массивов.

        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        # Объединяем массивы и сортируем
        combined = sorted(nums1 + nums2)
        
        # Находим медиану
        n = len(combined)
        if n % 2 == 0:
            # Если количество элементов четное, медианой является среднее двух центральных элементов
            return (combined[n//2 - 1] + combined[n//2]) / 2.0
        else:
            # Если количество элементов нечетное, медианой является центральный элемент
            return combined[n//2]

Объяснение кода

1. Начинаем с создания класса Solution, который будет содержать функцию поиска медианы.

2. В функции findMedianSortedArrays принимаем два отсортированных массива nums1 и nums2 в качестве входных параметров.

3. Далее объединяем эти два массива в один новый массив combined с помощью функции sorted(), которая сортирует элементы по возрастанию.

4. Затем находим длину объединенного массива combined и определяем, четное ли количество элементов в массиве.

5. Если количество элементов четное, медианой является среднее двух центральных элементов. Мы вычисляем это среднее и возвращаем результат в виде вещественного числа.

6. Если количество элементов нечетное, медианой является центральный элемент. Возвращаем этот центральный элемент.

Источник решения: hdhai.com