generated from interviews/template
79 lines
1.9 KiB
Go
79 lines
1.9 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("CASE A SHOULD BE 2:", medianOfArrays(
|
|
[]int{1, 3},
|
|
[]int{2},
|
|
))
|
|
log.Println("CASE B SHOULD BE 2.5:", 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 // [1, 2, 3] vs [2, 2, 2]
|
|
}
|
|
}
|
|
|
|
if mustGetAverage {
|
|
log.Println("need to avg lowest of", a[skippedA:], b[skippedB:])
|
|
fromA, lowest := getLowestOfArrays(a[skippedA:], b[skippedB:])
|
|
log.Println("got", fromA, lowest)
|
|
if fromA {
|
|
skippedA += 1
|
|
} else {
|
|
skippedB += 1
|
|
}
|
|
log.Println("'need to avg lowest of", a[skippedA:], b[skippedB:])
|
|
_, secondLowest := getLowestOfArrays(a[skippedA:], b[skippedB:])
|
|
log.Println("avg(", lowest, secondLowest)
|
|
return (float64(lowest) + float64(secondLowest)) / 2
|
|
}
|
|
_, lowest := getLowestOfArrays(a[skippedA:], b[skippedB:])
|
|
return float64(lowest)
|
|
}
|
|
|
|
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]
|
|
}
|