leetcode-go/leetcode/hard/480.sliding-window-median.go

type ints []int

func (is ints) search(x int) int {
	beg, end := 0, len(is)-1
	for beg <= end {
		mid := beg + (end-beg)/2
		if is[mid] < x {
			beg = mid + 1
		} else {
			end = mid - 1
		}
	}
	return beg
}

func (is *ints) insert(x int) {
	idx := is.search(x)
	if n := len(*is); idx == n {
		*is = append(*is, x)
	} else {
		nis := make([]int, n+1)
		copy(nis, (*is)[:idx])
		nis[idx] = x
		copy(nis[idx+1:], (*is)[idx:])
		*is = nis
	}
}

func (is *ints) delete(x int) {
	idx := is.search(x)
	if n := len(*is); idx == n-1 {
		*is = (*is)[:n-1]
	} else {
		copy((*is)[idx:], (*is)[idx+1:])
		*is = (*is)[:n-1]
	}
}

func medianSlidingWindow(nums []int, k int) (ans []float64) {
	n := len(nums)
	if n < k || k == 0 {
		return
	}
	var win ints = make([]int, 0)
	for i := 0; i < n; i++ {
		if k <= i {
			win.delete(nums[i-k])
		}
		win.insert(nums[i])
		if k-1 <= i {
			if k%2 == 1 {
				ans = append(ans, float64(win[k/2]))
			} else {
				ans = append(ans, float64(win[k/2-1]+win[k/2])/2.0)
			}
		}
	}
	return
}