题解 | #设计LFU缓存结构# 满足O(logn)复杂度

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * lfu design
 * @param operators int整型二维数组 ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
func LFU(operators [][]int, k int) []int {
	// write code here
	h := Heap{
		capValue: k,
		lenValue: 0,
		ts:       0,
		arr:      make([]*Ele, k),
		m:        make(map[int]int, k),
	}

	res := make([]int, 0, 2)
	for _, v := range operators {
		if v[0] == 1 {
			h.Set(v[1], v[2])
		} else {
			subRes := h.Get(v[1])
			res = append(res, subRes)
		}
	}

	return res
}

//       2
//    5      10
//  12  18  11  19
// 2 5 10 12 18 11 19

type Ele struct {
	k     int
	v     int
	ts    int
	count int
}

func (e *Ele) operateIncr(ts int) {
	e.ts = ts
	e.count++
}

func (e *Ele) IsGT(v *Ele) bool {
	if e.count > v.count {
		return true
	} else if e.count < v.count {
		return false
	}

	return e.ts > v.ts
}

type Heap struct {
	capValue int
	lenValue int
	ts       int
	arr      []*Ele
	m        map[int]int
}

func (h *Heap) Set(k, v int) {
	h.Incr()
	// 如果存在
	if i, ok := h.m[k]; ok {
		e := h.arr[i]
		e.operateIncr(h.ts)
		e.v = v
		h.Heapify(i)
		return
	}

	// 已满
	if h.lenValue == h.capValue {
		h.Pop()
	}

	// 未满
	h.m[k] = h.lenValue
	h.arr[h.lenValue] = &Ele{
		k:     k,
		v:     v,
		ts:    h.ts,
		count: 1,
	}
	h.lenValue++
	h.Heap()
}

func (h *Heap) Get(k int) int {
	h.Incr()
	if i, ok := h.m[k]; ok {
		e := h.arr[i]
		e.operateIncr(h.ts)
		h.Heapify(i)
		return e.v
	}
	return -1
}

func (h *Heap) Heapify(i int) {
	li := 2*i + 1
	ri := 2*i + 2
	iv := h.arr[i]
	if ri < h.lenValue {
		lv := h.arr[li]
		rv := h.arr[ri]
		if lv.IsGT(rv) && iv.IsGT(rv) {
			h.Swap(ri, i)
			h.Heapify(ri)
		} else if iv.IsGT(lv) {
			h.Swap(li, i)
			h.Heapify(li)
		}
	} else if li < h.lenValue {
		lv := h.arr[li]
		if iv.IsGT(lv) {
			h.Swap(li, i)
			h.Heapify(li)
		}
	}
}

func (h *Heap) Heap() {
	i := h.lenValue - 1
	for {
		v := h.arr[i]
		if i > 0 {
			pi := (i - 1) / 2
			pv := h.arr[pi]
			if pv.IsGT(v) {
				h.Swap(i, pi)
				i = pi
			} else {
				return
			}
		} else {
			return
		}
	}
}

func (h *Heap) Pop() {
	h.lenValue--
	h.Swap(h.lenValue, 0)
	h.Heapify(0)
	delete(h.m, h.arr[h.lenValue].k)
}

func (h *Heap) Incr() {
	h.ts++
}

func (h *Heap) Swap(i, j int) {
	h.arr[i], h.arr[j] = h.arr[j], h.arr[i]
	h.m[h.arr[i].k] = i
	h.m[h.arr[j].k] = j
}