这篇文章主要介绍了golang刷leetcode技巧之如何实现全 O(1) 的数据结构，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。
请你实现一个数据结构支持以下操作：
Inc(key) – 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
Dec(key) – 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否则使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
GetMaxKey() – 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串"" 。
GetMinKey() – 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。
挑战：
你能够以 O(1) 的时间复杂度实现所有操作吗？
解题思路
1，这是lru的变体，用hash＋有序双链表的形式
2，每次inc和dec的时候将当前节点从链表中去除
3，然后找到合适的位置插入
4，注意，当inc后，后面的连续常数个值相等，需要特殊处理
5，dec类似
代码实现
type Node struct{next *Nodeprev *Nodeval intkey string}type AllOne struct {head *Nodetail *Nodem map[string]*Node}/** Initialize your data structure here. */func Constructor() AllOne {ao:=AllOne{head:&Node{},tail:&Node{},m:make(map[string]*Node),}ao.head.next=ao.tailao.tail.prev=ao.headreturn ao}/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */func (this *AllOne) Inc(key string) {if n,ok:=this.m[key];ok{this.m[key].val++next:=n.nextif next==this.tail || next.val>=n.val{return}else{next.prev=n.prevn.prev.next=nextfor next.next!=this.tail && next.next.val<n.val{next=next.next}n.next=next.nextn.prev=nextnext.next.prev=nnext.next=n}}else{n:=&Node{val:1,key:key,prev:this.head,next:this.head.next,}this.head.next.prev=nthis.head.next=nthis.m[key]=n}this.Print()}func(this*AllOne)Print(){for n:=this.head.next ;n!=this.tail;n=n.next{println(n.val)}}/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */func (this *AllOne) Dec(key string) {if _,ok:=this.m[key];!ok {return}n:= this.m[key]if this.m[key].val>1{n.val--if n.prev==this.head || n.prev.val<=n.val{return}else {prev:=n.prevprev.next=n.nextn.next.prev=prevfor prev.prev!=this.head && prev.prev.val>n.val{prev=prev.prev}n.prev=prev.prevn.next=prevprev.prev.next=nprev.prev=n}}else{n.prev.next=n.nextn.next.prev=n.prevdelete(this.m,key)}this.Print()}/** Returns one of the keys with maximal value. */func (this *AllOne) GetMaxKey() string {if this.head.next==this.tail{return ""}return this.tail.prev.key}/** Returns one of the keys with Minimal value. */func (this *AllOne) GetMinKey() string {if this.head.next==this.tail{return ""}return this.head.next.key}/*** Your AllOne object will be instantiated and called as such:* obj := Constructor();* obj.Inc(key);* obj.Dec(key);* param_3 := obj.GetMaxKey();* param_4 := obj.GetMinKey();*/
感谢你能够认真阅读完这篇文章，希望小编分享的“golang刷leetcode技巧之如何实现全 O(1) 的数据结构”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!
原创文章，作者：kepupublish，如若转载，请注明出处：https://blog.ytso.com/223987.html