Я вот подумал, а почему бы мне не попробовать решить задачу с LeetCode с уровнем сложности hard. А собственно говоря, чего думать, надо брать и решать. Погнали. Посмотреть решения других задач с LeetCode можно в специальной рубрике «Решаем задачи» на сайте touch-it.ru.
Стоп, буквально пару слов о себе. Меня зовут Кирилл, я начинающий Python-разработчик. Я открыт ко всему новому, в том числе и к вашим предложениям о сотрудничестве. Познакомиться с моим портфолио на GitHub можно вот по этой ссылке, а связаться со мной можно в Telegram: @Kirill_Barabanshchikov
Условия задачи
Median of two sorted arrays: дано два отсортированных массива с длиной n и m. Нужно вернуть медиану двух этих массивов. Временная сложность O(log (m+n)).
Например, программа на вход получает два массива [1, 3], [2]. Оба массива отсортированы. Медианное значение двух объединенных массивов будет равно 2, а сам объединенный массив будет выглядеть так: [1, 2, 3].
Ограничения (constraints): массивы могут быть пустыми. Максимальная длина каждого из массивов не может превышать 1000 элементов. Следовательно, максимальная длина объединенного массива не может превышать 2000 элементов. При этом, объединенный массив не может состоять меньше, чем из одного элемента.
Немного теории
Прежде чем начинать искать непосредственно само решение, следует напомнить, а может и узнать, что такое медианное значение и как его находить.
Медианное значение
Согласно Википедии, медиана, в контексте статистики, представляет собой серединное значение набора чисел. Медианное значение — это такое значение, которое в упорядоченном по возрастанию наборе чисел будет больше числа слева и меньше числа справа.
С помощью медианы в статистике можно добиться получения более точных данных, что существенным образом влияет на их дальнейшую интерпретацию. Медиана лишена недостатков среднего арифметического значения.
Нахождение медианного значения
Алгоритм нахождения медианного значения будет зависеть от того, четное или нечетное количество элементов содержится в массиве.
Если массив содержит нечетное количество элементов, то медианным значением данного массива будет его центральный элемент.
При четном количестве элементов берется среднее арифметическое значение двух центральных элементов.
Метод нахождения медианы
Чтобы не писать весь код в одном методе класса Solution, вынесу поиск медианного значения в отдельный метод, что позволит многократно к нему обращаться без дублирования кода. Метод назову search_median_value().
В качестве аргумента метод принимает отсортированный список, а возвращает медианное значение. Как работает метод:
- шаг 1: определение длины полученного списка. Определение длины списка имеет линейную сложность, то есть O(n);
- шаг 2: определение индекса центрального элемента. Используется целочисленное деление “//”;
- шаг 3: определяю, содержит массив четное или нечетное количество элементов. Для этого использую деление по модулю (остаток от деления) — «%»;
- шаг 3.1: если список содержит четное количество элементов, то медианное значение находим как среднее арифметическое двух центральных элементов;
- шаг 3.2: если список содержит нечетное количество элементов, то нам просто нужно взять центральный элемент по индексу, который я рассчитал на шаге 2. Получение элемента списка по индексу имеет константную сложность – O(1).
Полный код метода search_median_value():
def search_median_value(self, search_array):
"""Метод определения медианного значения в отсортированном списке."""
# Определение длины полученного списка
length_search_array = len(search_array)
# определение индекса центрального элемента списка
mid_index = length_search_array // 2
# Определение медианного значения. Метод определения
# зависит от четности (нечетности) элементов в списке
if length_search_array % 2 == 0:
median_value = (
search_array[mid_index] + search_array[mid_index - 1]
) / 2
return median_value
return search_array[mid_index]
Дальнейшие размышления
Есть два отсортированных списка. Первое, что приходит в голову, — это их соединить и дальше работать с одним списком. Но просто соединить — это не совсем то.
Дело в том, что при простом сложении списков мы получим неотсортированный список, а искать медианное значение необходимо в отсортированном списке. Следовательно, такой список придется еще и сортировать, а это скажется на временной сложности решения.
А что если, не просто сложить списки, а, используя наше знание о том, что списки отсортированы, встроить один список в другой? Звучит вроде неплохо, осталось понять, как это реализовать на практике.
Простой случай сложения списков
Самый простой случай — когда последний элемент одного списка меньше или равен первому элементу второго списка. Тогда списки можно будет просто сложить, и в результате получится общий отсортированный список.
Отсортированный список можно уже будет спокойно передать в работу методу search_median_value() и ждать результата его работы.
На примере двух списков [1, 2] и [3, 4] или [1, 2, 3] и [4, 5] мой подход работает, но этого мало. Кстати, ситуация может быть обратной, например, когда на вход мы получаем списки [3, 4] и [1, 2]. Но это также несложно обработать. Вот код, который пока получился.
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
"""Метод поиска медианного значения в двух отсортированных списках."""
# сложение двух отсортированных списков, в которых
# последний элемент списка nums1 меньше или равен
# первому элементу списка nums2
last_element_nums1 = nums1[-1]
first_element_nums2 = nums2[0]
if last_element_nums1 <= first_element_nums2:
return self.search_median_value(nums1 + nums2)
# сложение двух отсортированных списков, в которых
# последний элемент списка nums2 меньше или равен
# первому элементу списка nums1
first_element_nums1 = nums1[0]
last_element_nums2 = nums2[-1]
if last_element_nums2 <= first_element_nums1:
return self.search_median_value(nums2 + nums1)
Неудачное просветление
Слушайте, а если вообще обойтись без встраивания списков?
Что, если найти медианное значение каждого из списков, а потом найти среднее арифметическое найденных медианных значений? Чего собственно гадать, давайте пробовать, все для этого имеется.
Реализация несложная, передаем каждый из списков в метод поиска медианного значения, а далее рассчитываем среднее арифметическое значения полученных медиан.
Вот такой блок кода получился:
def findMedianSortedArrays( self, nums1: List[int], nums2: List[int]) -> float:
"""Метод поиска медианного значения в двух отсортированных списках."""
...
# Получение медианного значения первого списка
median_value_nums1 = self.search_median_value(nums1)
# Получение медианного значения второго списка
median_value_nums2 = self.search_median_value(nums2)
# Поиск среднеарифметического значения двух медианных значений
return (median_value_nums1 + median_value_nums2) / 2
И да, этот способ дал результаты, но я забыл обработать граничные значения, о чем мне сообщают результаты тестов. Себе на заметку: надо все же сразу задумываться над такими граничными значениями и обрабатывать их.
Про крайности
По условиям задачи списки могут быть пустыми, но объединенный список в любом случае должен состоять, как минимум, из одного элемента. А это значит, что как минимум один список будет с элементами (элементом). Значит, в таком списке и буду искать медианное значение.
def findMedianSortedArrays( self, nums1: List[int], nums2: List[int]) -> float:
"""Метод поиска медианного значения в двух отсортированных списках."""
# Обработка случая, когда оба списка пустые
if not nums1:
return self.search_median_value(nums2)
if not nums2:
return self.search_median_value(nums1)
Возвращаюсь к рассуждениям
Мой подход прошел 804 теста из 2094 и сломался на списках [1, 3] и [2, 7]. Мое решение выдает 3.25, а верный ответ, 2.5.
Объединенный список должен выглядеть так: [1, 2, 3, 7]. Список имеет четное количество элементов, следовательно, медианное значение будет равно (2 + 3) / 2, то есть, 2.5.
Из этого отрицательного результата, а как мы знаем, отрицательный результат – это тоже результат, можно сделать вывод, что списки все же нужно объединять, вопрос только как?
Про сортировку
Для эксперимента предлагаю попробовать самый простой вариант. Речь идет об использовании встроенной функции sorted(). А в качестве аргумента этой функции я передам сумму двух списков.
Такой подход должен сработать, но открытым остается вопрос об его сложности. По условиям задачи, наш предел – линейно-логарифмическая сложность.
Результаты:
- Runtime: 77 ms. Beats 75.78% of users with Python3
- Memory: 16.86 MB. Beats 76.30% of users with Python3
Собственно, что и требовалось доказать. Все тесты пройдены, и даже показатели работы решения вполне достойные. Но вот чувства удовлетворения у меня не появилось. Мне кажется, что это не совсем то решение, которое авторы задачи ждут.
Раз уж я тут экспериментирую, то хочется попробовать удалить ту часть кода, которая соединяет списки в один, при условии, что списки не входят друг в друга (этот вариант я описывал выше).
И да, это решение тоже принято. Более того, оно оказалось немножечко быстрее, но тут все в пределах нескольких миллисекунд. Будем считать, что результаты решений равнозначны.
Результаты:
- Runtime: 80 ms. Beats 60.73% of users with Python3
- Memory: 16.70 MB. Beats 99.64% of users with Python3
Что ж, предлагаю остановиться на этом решении и подробнее взглянуть на функцию sorted().
Функция sorted()
Согласно документации (раздел “Sorting Techniques”) функция sorted() сортирует список по возрастанию. Функция принимает в качестве аргумента итерируемый объект и возвращает вновь созданный отсортированный список.
Функция sorted() обеспечивает эффективный способ организации данных в заданном порядке. По умолчанию сортировка происходит по возрастанию.
Синтаксис функции sorted():
sorted(iterable, key=None, reverse=False)
Временная сложность функции sorted() равна O(n log(n)) для наихудшего и среднего случая и o(n) – для лучшего случая. Лучшим случаем является получение на вход частично отсортированных списков. По всей видимости, именно эта характеристика помогла пройти тесты на LeetCode.
Timsort – то, что работает под капотом
Взглянем под капот функции sorted() и, хотя бы в общих чертах, посмотрим, какой алгоритм используется в ней.
Timsort представляет собой встроенный в Python гибридный алгоритм сортировки. Гибридность объясняется тем, что на больших объемах данных используется сортировка слиянием, а на малых объемах – сортировка вставками.
Алгоритм находит подпоследовательности, которые уже отсортированы и использует их для наиболее эффективной сортировки остатка.
Кратко об этапах работы алгоритма:
- разделение входного массива на массивы фиксированной длины;
- каждый из массивов сортируется наиболее эффективным образом;
- отсортированные массивы объединяются в один массив. Объединение осуществляется с помощью специальной реализации алгоритма сортировки слиянием.
Подробно описывать работу алгоритма Timsort не буду. Про это можно почитать здесь и здесь.
Полный код решения задачи Median of two sorted arrays:
from typing import List
class Solution:
def search_median_value(self, search_array):
"""Метод определения медианного значения в отсортированном списке."""
# Определение длины полученного списка
length_search_array = len(search_array)
# определение индекса центрального элемента списка
mid_index = length_search_array // 2
# Определение медианного значения. Метод определения
# зависит от четности (нечетности) элементов в списке
if length_search_array % 2 == 0:
median_value = (
search_array[mid_index] + search_array[mid_index - 1]
) / 2
return median_value
return search_array[mid_index]
def findMedianSortedArrays(
self, nums1: List[int], nums2: List[int]
) -> float:
# Обработка случая, когда оба списка пустые
if not nums1:
return self.search_median_value(nums2)
if not nums2:
return self.search_median_value(nums1)
# сложение двух отсортированных списков, в которых
# последний элемент списка nums1 меньше или равен
# первому элементу списка nums2
last_element_nums1 = nums1[-1]
first_element_nums2 = nums2[0]
if last_element_nums1 <= first_element_nums2:
return self.search_median_value(nums1 + nums2)
# сложение двух отсортированных списков, в которых
# последний элемент списка nums2 меньше или равен
# первому элементу списка nums1
first_element_nums1 = nums1[0]
last_element_nums2 = nums2[-1]
if last_element_nums2 <= first_element_nums1:
return self.search_median_value(nums2 + nums1)
search_array = sorted(nums1 + nums2)
median_value = self.search_median_value(search_array)
return median_value
В качестве заключения
Не смотря на то, что задача решена, я остался не совсем доволен решением. Есть у меня ощущение, что есть более эффективное решение.
Хотя стоит отметить, что пока работал над этой задачей, неоднократно попадались мнения, что используемый алгоритм в функции sorted() является достаточно эффективным и его пользовательские вариации далеко не всегда будут эффективнее.
В любом случае, было интересно и полезно. Впереди еще много чего нужно изучить в области сортировки, так как это важный элемент работы при обработке больших объемов данных.