Median of Two Sorted Arrays
Тебе даны два списка целых чисел, nums1 и nums2, каждый отсортирован от меньшего к большему и содержит как минимум одно значение. Верни медиану всех их значений вместе в виде текста.
При нечётном общем количестве медиана — это среднее значение, например "4". При чётном количестве это среднее арифметическое двух средних значений, например "2.5" или "-0.5". Записывай целое число без десятичной точки, а ноль — как "0", никогда как "-0". Стремись к временной сложности O(log(min(m, n))).
Функция
- nums1integer-array
- первый список, отсортированный от меньшего к большему
- nums2integer-array
- второй список, отсортированный от наименьшего к наибольшему
- Возвращаетstring
- медиана всех значений в виде текста, например «4» или «-2.5»
Ограничения
1 ≤ nums1.length, nums2.length ≤ 3000-106 ≤ nums1[i], nums2[i] ≤ 106- Оба списка отсортированы в неубывающем порядке, значения могут повторяться.
Примеры
- Ввод
- nums1 = [1, 4]nums2 = [2, 7, 9]
- Вывод
- "4"
- Пояснение
- Вместе значения составляют 1, 2, 4, 7, 9. У пяти значений есть одно среднее значение — третье, это 4.
- Ввод
- nums1 = [1, 2]nums2 = [3, 4]
- Вывод
- "2.5"
- Пояснение
- Вместе значения составляют 1, 2, 3, 4. Два средних значения — 2 и 3, их сумма равна 5, а половина от 5 — 2.5.
- Ввод
- nums1 = [-7, -3]nums2 = [-2, 0]
- Вывод
- "-2.5"
- Пояснение
- Вместе значения составляют -7, -3, -2, 0. Средние значения -3 и -2 в сумме дают -5, а половина от -5 — это -2.5.
Дополнительный вопрос
Можешь ли ты использовать тот же разрез, чтобы найти k-е наименьшее значение в двух списках для любого k за логарифмическое время?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Объединение двух списков позволяет найти медиану за
O(m + n). Чтобы сделать это быстрее, представь медиану как границу: линию, которая делит всеm + nзначений на нижнюю и верхнюю половины одинакового размера.Нижняя половина — это префикс
nums1плюс префиксnums2. Если изnums1берётсяiзначений, то количество значений изnums2определяется автоматически. Разделение верное, если последнее взятое значение из каждого списка не больше первого оставшегося значения в другом списке.Выполни бинарный поиск по
iв более коротком списке. Если последнее взятое значение изnums1слишком велико, возьми из него меньше значений; если последнее значение изnums2слишком велико, возьми больше. При правильном разделении медиана определяется наибольшим значением ниже разделения и наименьшим выше него. Сложи эти два целых числа и сам раздели сумму пополам.
Решение
Объединение списков позволяет найти медиану за O(m + n), но большинство прочитанных значений не может повлиять на ответ. Медиана зависит только от того, где проходит граница между нижней и верхней половинами, и эту границу определяет одно число: сколько значений нижняя половина берет из более короткого списка. Двоичный поиск находит его за O(log(min(m, n)) шагов.
Объедините два списка
Идея
Объедините списки, как это делает сортировка слиянием, в один отсортированный список merged. При total = m + n сложите merged[(total-1)/2] и merged[total/2], используя целочисленное деление. При нечётном общем количестве оба значения будут средним элементом, а при чётном — двумя средними элементами, поэтому в любом случае половина суммы будет медианой.
Даже если остановиться на середине, при слиянии нужно пройти больше половины значений, поэтому время выполнения составляет O(m + n).
Алгоритм
- Объедини списки в
merged, каждый раз выбирая меньшее из текущих значений, а затем добавь оставшуюся часть списка. - При
total = m + nсложиmerged[(total-1)/2]иmerged[total/2]. - Запиши половину суммы в виде текста: чётную сумму раздели на 2; для нечётной суммы запиши знак, половину абсолютного значения и
.5.
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Merge the two sorted lists into one, the way merge sort does.
merged = []
i = j = 0
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
merged.extend(nums1[i:])
merged.extend(nums2[j:])
total = len(merged)
# For an odd total both indexes point at the one middle value.
return half_text(merged[(total - 1) // 2] + merged[total // 2])Бинарный поиск по точке разреза
Идея
Пусть в нижней половине будет half = (m+n+1)/2 значений — на одно больше, если общее количество нечётное. Из начала nums1 берутся i значений, а из начала nums2 — j = half-i. Разрез верен, если ни одно значение снизу не больше ни одного значения сверху. Каждый список отсортирован, поэтому остаются две проверки: left1 ≤ right2 и left2 ≤ right1, где left — последнее значение, которое список отдаёт нижней половине, а right — первое значение, которое он оставляет. Отсутствующая граница считается минус или плюс бесконечностью.
Если left1 > right2, значение i слишком велико; если left2 > right1 — слишком мало. Значит, для i выполняется бинарный поиск в диапазоне от 0 до m. Для [1, 2] и [3, 4] значение i = 1 не подходит из-за условия left2 = 3 > right1 = 2, а i = 2 подходит: (2 + 3) / 2 = 2.5.
Алгоритм
- Сделай
nums1более коротким списком; пустьhalf = (m+n+1)/2. - Выполняй двоичный поиск
iотlo = 0доhi = m, гдеj = half-i. - Считай
left1 = nums1[i-1],right1 = nums1[i],left2 = nums2[j-1]иright2 = nums2[j], считая, что за концом списка находится бесконечность. - Если
left1 > right2, установиhi = i-1. Еслиleft2 > right1, установиlo = i+1. - В противном случае, если общее количество элементов нечётное, верни
max(left1, left2). Если оно чётное, разделиmax(left1, left2) + min(right1, right2)пополам, как текст.
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Binary search over the shorter list.
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2 # size of the left half; it gets the extra value when m + n is odd
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # values the left half takes from nums1
j = half - i # values it takes from nums2
# An empty side counts as minus or plus infinity.
left1 = nums1[i - 1] if i > 0 else float("-inf")
right1 = nums1[i] if i < m else float("inf")
left2 = nums2[j - 1] if j > 0 else float("-inf")
right2 = nums2[j] if j < n else float("inf")
if left1 > right2:
hi = i - 1 # too many values from nums1
elif left2 > right1:
lo = i + 1 # too few values from nums1
else:
left_max = max(left1, left2)
if (m + n) % 2 == 1:
return str(left_max)
return half_text(left_max + min(right1, right2))
return "" # not reached: sorted input always has a valid split
Ловушки и крайние случаи
- Деление пополам с плавающей точкой. Python выводит целую медиану как
3.0, а%fв C выводит 2.5 как2.500000. Храни сумму как целое число. - Запись целого частного и
.5для отрицательной нечётной суммы.-1 / 2равно 0 в C и Java, поэтому для -0.5 получится 0.5;-5 // 2равно -3 в Python, поэтому для -2.5 получится -3.5. Раздели абсолютное значение пополам и верни знак. - Запись
-0. Средние значения -1 и 1 в сумме дают 0, и ответ —"0". Определи знак по сумме. - Поиск в более длинном списке.
j = half-iможет стать меньше 0 или превыситьn. Сначала поменяй списки местами. - Чтение
nums1[i-1]приi = 0, как для[9]и[1, 2]. Для отсутствующих значений используй бесконечности.
Частые вопросы3
Какова временная сложность алгоритма поиска медианы двух отсортированных массивов?
Двоичный поиск точки разреза занимает O(log(min(m, n))) времени и O(1) памяти, поскольку на каждом шаге количество возможных точек разреза в более коротком списке уменьшается вдвое. Слияние занимает O(m + n): для двух списков по 3000 элементов — около 12 шагов вместо 6000.
Почему бинарный поиск выполняется по более короткому массиву?
Поскольку j = half-i. Когда i пробегает более короткий список, j остаётся в диапазоне от 0 до длины более длинного списка, поэтому каждое чтение происходит в пределах списка или за его концом, который ты считаешь бесконечностью.
Как вернуть медиану без чисел с плавающей точкой?
Сложи два средних значения как целые числа. Раздели чётную сумму на 2. Для нечётной суммы запиши половину её абсолютного значения и .5, добавив знак минус, если сумма отрицательная: -1 превращается в "-0.5".
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def findMedianSortedArrays(nums1, nums2):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргументы
nums1 = [1, 4] nums2 = [2, 7, 9]
Ожидаемый вывод
"4"