Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

 

Example 1:

Input: nums1 = [1,3], nums2 = [2]

Output: 2.00000

Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]

Output: 2.50000

Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Решение:

class Solution:

def findMedianSortedArrays(self,

nums1: List[int],

nums2: List[int]) -> float:

# Первым массивом всегда должен быть самый короткий

if len(nums1) > len(nums2):

nums1, nums2 = nums2, nums1

# Длины массивов

x, y = len(nums1), len(nums2)

# Границы применения бисекции, не длонее длинны короткого массива

low, high = 0, x

while low <= high:

# Точка разбиения в массиве nums1

partitionX = (low + high) // 2

# Точка разбиения в массиве nums2

partitionY = (x + y + 1) // 2 - partitionX

maxX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]

minX = float('inf') if partitionX == x else nums1[partitionX]

maxY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]

minY = float('inf') if partitionY == y else nums2[partitionY]

if maxX <= minY and maxY <= minX:

if (x + y) % 2 == 0:

return (max(maxX, maxY) + min(minX, minY)) / 2

else:

return max(maxX, maxY)

elif maxX > minY:

high = partitionX - 1

else:

low = partitionX + 1

Идея решения 1:

Особый случай - длинна обеих входных массивов 0, значит сразу возвратить None, так как у таких данных медианы нет.

Далее размышления на примере:

A[1, 3, 5, 7]

B[2, 6, 10]

Ответ: 5

Берутся крайние элементы обеих массивов. Когда массивы большие - это 4 числа. Но далее в итерациях может быть и меньше вплоть до 1 числа (если один или оба массивов длинной 1 или даже длинной 0).

Для A берутся числа 1, 7

Для B берутся числа 2, 10

Из этих чисел делается массив крайних элементов и упорядочивается: [1, 2, 7, 10]. Искомое значение медианы будет в середине данного массива, то есть, где-то между числами 2 и 7 (включая сами эти числа).

Зная это, можно расматривать только те элементы массивов, которые находятся в диапазоне 2...7.

Для A надо рассматривать A[3, 5, 7]

Для B надо рассматривать B[2, 6]

Примечание: чтобы не делать копирования массивов, для каждого массива надо только хранить левый и правый "указатель" на обрабатываемый диапазон. Причем левый указатель может двигаться только вправо или стоять на месте, а правый указатель - только влево или стоять на месте.

Снова берутся крайние элементы обеих массивов и упорядываются:

Для A берутся числа 3, 7

Для B берутся числа 2, 6

Снова делается массив крайних элементов из этих чисел и упорядовачивается: [2, 3, 6, 7]. Искомое значение медианы будет в середине данного массива, то есть, где-то между числами 3 и 6 (включая сами эти числа).

Тким образом, в массивах A и B надо рассматривать диапазон между 3 и 6.

Для A надо рассматривать A[3, 5]

Для B надо рассматривать B[6]

Общее количество элементов - 3, то есть, меньше 4-х. Это значит, что можно звершать расчет.

Как звершается расчет?

Делается массив из этих чисел и упорядовачивается: [3, 5, 6]. Так как элементов 3, то ответ четко в середине, то есть 5.

Если останется общее количество элементов 2, то ответом будет арифметическое среднее между этими двумя числами.

Если останется общее количество элементов 1, то ответом будет это единственное значение.

Особые указания

Когда формируется массив из крайних элементов, надо учитывать, что исходный массив A или B может быть нуливой или единичной длинны.

При нуливой длинне в массив крайних элементов ничего не добавляется.

При единичной длинне добавляется одно значение.

Добавляемые числа могут быть одинаковые, поэтому из массива крайних элементов надо убирать повторения? Таким образом, массив крайних элементов в в середине итераций может содержать и количество элементов меньше, чем 4.

Если M[i, j, k, h] - в качестве диапазона берется j и k

Если M[i, j, k] - в качестве диапазона берется j и k

Идея решения 2:

Мы рассмотрим следующие два упорядоченных массива:

nums1 {1,3,7,8,10}

nums2 {2,4,6,9}

Ответ: медиана объединенного массива {1,2,3,4,6,7,8,9,10} равна 6.

Как получить этот ответ?

Сначала поместить короткий массив вперед:

Предположим, что nums1 теперь {2,4,6,9}, а nums2 - {1,3,7,8,10}

Рассчитать сумму длин двух массивов, она будет равна sumLen=9.

Это число нечетное, поэтому индекс разбиения надо взять как целочислительный k = sumLen / 2 + 1. То есть k = 5.

Это означает, что нужно найти пятое число после объединения и сортировки двух массивов.

Из первого массива берется число по индексу k/2=5/2=2 (этот индекс обозначается как p1=2, используется целочисленное деление). То есть берется значение num1[p1]=num1[2]=4 (счет индексов с единицы?)

Для второго массива берется число по индексу k-p1, то есть num2[k-p1]=num2[5-2]=num2[3]=7 (счет индексов с единицы?)

Сравнить числа, взятые из nums1 и nums2: то есть сравнить 4 и 7.

Дальше белиберда.

Найдено, что 4 меньше 7, поэтому сначала мы берем числа 2 и 4 из nums1 и возвращаем 1,3,7 к нашему рассмотрению.

В настоящее время, поскольку 2 были удалены, поэтому k = 5-2 = 3, то есть нам нужно только взять еще три числа.

Возвращаясь к исходному методу, в соответствии с 3/2 = 1, поэтому 1 в nums1 и 3-1 = 2 в nums2:

6> 3 в это время найдено, поэтому уберите 1,3 в nums2. k = 3-2 = 1, то есть мы можем взять еще один.

Очевидно, возьмите меньшее из первого элемента nums1 и первого элемента nums2:

Наконец получил ответ: 6.

Идея решения 3:

Написать согласно алгоритму решения.