generated from interviews/template
90 lines
2.1 KiB
Go
90 lines
2.1 KiB
Go
// Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
|
|
|
|
// Input: nums1 = [1,3], nums2 = [2]
|
|
// Output: 2.00000
|
|
// Explanation: merged array = [1,2,3] and median is 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.
|
|
|
|
package main
|
|
|
|
import "log"
|
|
|
|
func main() {
|
|
log.Println(medianOfArrays(
|
|
[]int{1, 3},
|
|
[]int{2},
|
|
))
|
|
log.Println(medianOfArrays(
|
|
[]int{1, 2},
|
|
[]int{3, 4},
|
|
))
|
|
}
|
|
|
|
func medianOfArrays(a, b []int) float64 {
|
|
valueCount := len(a) + len(b)
|
|
mustGetAverage := (valueCount%2 == 0)
|
|
needToSkip := valueCount / 2
|
|
if !mustGetAverage {
|
|
needToSkip += 1
|
|
}
|
|
needToSkip -= 1
|
|
|
|
skippedA, skippedB := 0, 0
|
|
for needToSkip > skippedA+skippedB {
|
|
log.Println(needToSkip, skippedA, skippedB)
|
|
aExhausted := skippedA >= len(a)
|
|
bExhausted := skippedB >= len(b)
|
|
if aExhausted || b[skippedB] < a[skippedA] {
|
|
skippedB += 1
|
|
} else if bExhausted || a[skippedA] < b[skippedB] {
|
|
skippedA += 1
|
|
} else if !aExhausted && !bExhausted {
|
|
skippedA += 1
|
|
}
|
|
}
|
|
|
|
log.Println(needToSkip, a, skippedA, b, skippedB)
|
|
if bothArraysHaveValues := skippedA < len(a) && skippedB < len(b); bothArraysHaveValues {
|
|
if mustGetAverage {
|
|
log.Println("need to avg lowest of", a[:skippedA], b[:skippedB])
|
|
fromA, lowest := getLowestOfArrays(a[skippedA:], b[skippedB:])
|
|
if fromA {
|
|
skippedA += 1
|
|
} else {
|
|
skippedB += 1
|
|
}
|
|
_, secondLowest := getLowestOfArrays(a[skippedA:], b[skippedB:])
|
|
return float64(lowest) + float64(secondLowest)/2
|
|
}
|
|
_, lowest := getLowestOfArrays(a[skippedA:], b[skippedB:])
|
|
return float64(lowest)
|
|
}
|
|
|
|
if aExhausted := skippedA >= len(a); aExhausted {
|
|
if mustGetAverage {
|
|
panic("not impl")
|
|
}
|
|
return float64(b[skippedB])
|
|
}
|
|
if mustGetAverage {
|
|
panic("not impl")
|
|
}
|
|
return float64(a[skippedA])
|
|
}
|
|
|
|
func getLowestOfArrays(a, b []int) (fromA bool, lowest int) {
|
|
if len(a) == 0 {
|
|
return false, b[0]
|
|
}
|
|
if len(b) == 0 {
|
|
return true, a[0]
|
|
}
|
|
if a[0] > b[0] {
|
|
return true, a[0]
|
|
}
|
|
return false, b[0]
|
|
}
|