4. Median of Two Sorted Arrays

#Array#Binary Search#Divide and Conquer

Даны два отсортированных массива nums1и nums2размером mи n соответственно, вернуть медиану двух отсортированных массивов.

Общая сложность времени выполнения должна быть O(log (m+n)).

Пример 1:

Ввод: nums1 = [1,3], nums2 = [2]
Вывод: 2,00000
Объяснение: объединенный массив = [1,2,3], а медиана равна 2.

Пример 2:

Ввод: nums1 = [1,2], nums2 = [3,4]
Вывод: 2,50000
Пояснение: объединенный массив = [1,2,3,4], а медиана равна (2 + 3) / 2 = 2,5.

Ограничения:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

Пример решения на go

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {

contArr:=len(nums1)+len(nums2)

var numCenter float64

numCenter = math.Round(float64(contArr)/2)

if contArr%2 != 0 {

return calcOne(nums1, nums2, numCenter)

}

return calcTwo(nums1, nums2, numCenter)

}

func calcOne(nums1, nums2 []int, numCenter float64) float64 {

index := int(numCenter)
var sub []int
var one, two, subElem int
var i int

for len(sub) < index {

one, two, subElem = get(nums1, nums2, one, two)
sub = append(sub, subElem)
i++

}

return float64(sub[index-1])

}

func calcTwo(nums1, nums2 []int, numCenter float64) float64 {

indexOne := int(math.Round(numCenter))
indexTwo := indexOne - 1

var sub []int
var one, two, subElem int
var i int

for len(sub) <= indexOne {

one, two, subElem = get(nums1, nums2, one, two)
sub = append(sub, subElem)
i++
}

sum:=sub[indexOne]+sub[indexTwo]

if sum == 0{

return 0

}

return float64(sum) / 2

}

func get(nums1, nums2 []int, one, two int) (int, int, int) {

var result int

if len(nums1) == 0 {
result = nums2[two]
two++
return one, two, result
}

if len(nums2) == 0 {
result = nums1[two]
two++
return one, two, result
}

if len(nums1) > one && len(nums2) > two && nums1[one] <= nums2[two] ||
len(nums1) >= one && len(nums2) <= two {

result = nums1[one]
one++
return one, two, result

}

if len(nums1) > one && len(nums2) > two && nums1[one] >= nums2[two] ||
len(nums1) <= one && len(nums2) >= two {

result = nums2[two]
two++
return one, two, result
}

panic("incorrect")

}