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