Median of Two Sorted Arrays

Сложная№4поиск разреза

Даны два отсортированных массива. Нужно найти медиану всех их чисел вместе — среднее по порядку число или полусумму двух средних, если чисел чётное количество, — за O(log(m + n)). Наш пример: a = [1, 5, 9, 12, 20], b = [2, 3, 7, 10, 15, 18] — 11 чисел, ответ 9.

4 Median of Two Sorted ArraysРазбор · 1×

Пример: a = [1, 5, 9, 12, 20], b = [2, 3, 7, 10, 15, 18]. Линии — разрезы: i чисел из a и j из b идут в левую половину. lo и hi ограничивают разрез в a.

a011529312420b021327310415518
идёт в левую половинуидёт в правую половинусравниваем у разрезовмедиана

a — более короткий массив, 5 чисел. Его разрез может взять от 0 до 5 из них: lo = 0

01/23
сначала · назад · пуск · шаг
Скорость
1function findMedian(a, b): // a is the shorter one
2 lo = 0
3 hi = len(a)
4 half = floor((len(a) + len(b) + 1) / 2)
5 while lo <= hi:
6 i = floor((lo + hi) / 2) // how many of a go left
7 j = half - i // the rest of the left half, from b
8 if a[i - 1] > b[j]: // past an end: −∞ or +∞
9 hi = i - 1 // too many from a
10 else if b[j - 1] > a[i]:
11 lo = i + 1 // too few from a
12 else: // every left number <= every right one
13 leftMax = max(a[i - 1], b[j - 1])
14 if (len(a) + len(b)) is odd:
15 return leftMax
16 return (leftMax + min(a[i], b[j])) / 2
состояние
lo
0
hi
–
half
–
i
–
j
–
leftMax
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Медиана делит все числа на две половины, где каждое левое не больше любого правого. Если из a взять i чисел, остальные half − i берутся из b, так что разрез в a один определяет всё разбиение.
  2. Каждый массив отсортирован, поэтому не в порядке могут быть только две пары: a[i − 1] с b[j] и b[j − 1] с a[i]. Если a[i − 1] > b[j], из a взяли слишком много, и разрез идёт влево; если b[j − 1] > a[i], слишком мало, и он идёт вправо. Это бинарный поиск по i.
  3. Поиск по более короткому массиву держит j между 0 и len(b). Здесь хватает трёх разрезов: 2 — мало, 4 — много, 3 — в самый раз.

Сложность

Время O(log(min(m, n))): бинарный поиск по разрезу в более коротком массиве. Память O(1): массивы не сливаются.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.