// 力扣
// 1. 双堆&&延迟删除
// 2. 线段树/树状数组 + 离散化
// 3. 朴素算法
// 4. skip list?
func lowbit(x int) int {
return x & (-x)
}
func add(p, c, n int, stat []int) {
for i := p; i <= n; i += lowbit(i) {
stat[i] += c
}
}
func sum(p int, stat []int) int {
ret := 0
for i := p; i > 0; i -= lowbit(i) {
ret += stat[i]
}
return ret
}
func findK(k, n int, stat []int) int {
l, r, ret := 1, n, -1
for l <= r {
mid := l + (r-l)/2
if sum(mid, stat) >= k {
ret, r = mid, mid-1
} else {
l = mid + 1
}
}
return ret
}
func medianSlidingWindow(nums []int, k int) []float64 {
n := len(nums)
cnums := make([]int, n)
copy(cnums, nums)
sort.Ints(cnums)
imap := make(map[int]int)
for i := 0; i < n; i++ {
imap[cnums[i]] = i + 1
}
stat := make([]int, n+1)
result := make([]float64, 0, n)
var findMedian = func(k int) float64 {
if k%2 == 0 {
idx1, idx2 := findK(k/2, n, stat)-1, findK(k/2+1, n, stat)-1
return float64(cnums[idx1]+cnums[idx2]) / 2.0
}
idx := findK((k+1)/2, n, stat) - 1
return float64(cnums[idx])
}
for i := 0; i < k; i++ {
add(imap[nums[i]], 1, n, stat)
}
result = append(result, findMedian(k))
for i := k; i < n; i++ {
add(imap[nums[i]], 1, n, stat)
add(imap[nums[i-k]], -1, n, stat)
result = append(result, findMedian(k))
}
return result
}
func pushUp(idx int, tree []int) {
tree[idx] = tree[idx<<1] + tree[(idx<<1)|1]
}
func query(k, s, t, idx int, tree []int) int {
if s == t {
return s
}
mid := (s + t) >> 1
if tree[idx<<1] >= k {
return query(k, s, mid, idx<<1, tree)
}
return query(k-tree[idx<<1], mid+1, t, idx<<1|1, tree)
}
func update(p, c, s, t, idx int, tree []int) {
if s == t {
tree[idx] += c
return
}
mid := (s + t) >> 1
if p <= mid {
update(p, c, s, mid, idx<<1, tree)
} else {
update(p, c, mid+1, t, (idx<<1)|1, tree)
}
pushUp(idx, tree)
}
func medianSlidingWindow(nums []int, k int) []float64 {
n := len(nums)
cnums := make([]int, n)
copy(cnums, nums)
sort.Ints(cnums)
imap := make(map[int]int)
for i := 0; i < n; i++ {
imap[cnums[i]] = i + 1
}
tree := make([]int, (n+10)<<2)
result := make([]float64, 0, n)
var findMedian = func(k int) float64 {
if k%2 == 0 {
idx1, idx2 := query(k/2, 1, n, 1, tree)-1, query(k/2+1, 1, n, 1, tree)-1
return float64(cnums[idx1]+cnums[idx2]) / 2.0
}
idx := query((k+1)/2, 1, n, 1, tree) - 1
return float64(cnums[idx])
}
for i := 0; i < k; i++ {
update(imap[nums[i]], 1, 1, n, 1, tree)
}
result = append(result, findMedian(k))
for i := k; i < n; i++ {
update(imap[nums[i]], 1, 1, n, 1, tree)
update(imap[nums[i-k]], -1, 1, n, 1, tree)
result = append(result, findMedian(k))
}
return result
}
type Item struct {
val int
idx int
}
type MaxPQ []*Item
func (pq MaxPQ) Len() int { return len(pq) }
func (pq MaxPQ) Less(i, j int) bool {
if pq[i].val == pq[j].val {
return pq[i].idx > pq[j].idx
}
return pq[i].val > pq[j].val
}
func (pq MaxPQ) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *MaxPQ) Push(x interface{}) {
item := x.(*Item)
*pq = append(*pq, item)
}
func (pq *MaxPQ) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}
func (pq *MaxPQ) Top() interface{} {
if pq.Len() == 0 {
return nil
}
return (*pq)[0]
}
type MinPQ []*Item
func (pq MinPQ) Len() int { return len(pq) }
func (pq MinPQ) Less(i, j int) bool {
if pq[i].val == pq[j].val {
return pq[i].idx < pq[j].idx
}
return pq[i].val < pq[j].val
}
func (pq MinPQ) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *MinPQ) Push(x interface{}) {
item := x.(*Item)
*pq = append(*pq, item)
}
func (pq *MinPQ) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}
func (pq *MinPQ) Top() interface{} {
if pq.Len() == 0 {
return nil
}
return (*pq)[0]
}
func medianSlidingWindow(nums []int, k int) []float64 {
var (
n = len(nums)
minHeap = make(MinPQ, 0) // 我擦他大爷,最大堆/最小堆写反了
maxHeap = make(MaxPQ, 0)
sz1 = 0
sz2 = 0
result = make([]float64, 0, n)
)
var add = func(val, idx int) {
if sz2 == 0 {
sz1++
heap.Push(&maxHeap, &Item{val, idx})
} else if sz1 == 0 {
sz2++
heap.Push(&minHeap, &Item{val, idx})
} else {
x := maxHeap.Top().(*Item)
if val < x.val {
sz1++
heap.Push(&maxHeap, &Item{val, idx})
} else {
sz2++
heap.Push(&minHeap, &Item{val, idx})
}
}
}
var adjust = func(idx int) {
if idx-k >= 0 {
if item, ok := maxHeap.Top().(*Item); ok && (item.val > nums[idx-k] || (item.val == nums[idx-k] && item.idx >= idx-k)) {
sz1--
} else {
sz2--
}
}
for sz1 > sz2+1 {
item := heap.Pop(&maxHeap).(*Item)
if item.idx <= idx-k {
continue
}
sz1--
sz2++
heap.Push(&minHeap, item)
}
for sz1+1 < sz2 {
item := heap.Pop(&minHeap).(*Item)
if item.idx <= idx-k {
continue
}
sz2--
sz1++
heap.Push(&maxHeap, item)
}
for maxHeap.Len() > 0 {
if item := maxHeap.Top().(*Item); item.idx <= idx-k {
heap.Pop(&maxHeap)
} else {
break
}
}
for minHeap.Len() > 0 {
if item := minHeap.Top().(*Item); item.idx <= idx-k {
heap.Pop(&minHeap)
} else {
break
}
}
}
var calc = func() float64 {
if sz1 == sz2 {
return float64(maxHeap.Top().(*Item).val+minHeap.Top().(*Item).val) / 2.0
} else if sz1 > sz2 {
return float64(maxHeap.Top().(*Item).val)
}
return float64(minHeap.Top().(*Item).val)
}
for i := 0; i < n; i++ {
add(nums[i], i)
adjust(i)
if i >= k-1 {
result = append(result, calc())
}
}
return result
}
// TODO: 周末搞个 skiplist 模板,复习一下。