golang刷leetcode技巧之如何实现全 O(1) 的数据结构

发布时间：2021-12-16 09:11:41 作者：小新
来源：亿速云阅读：138

这篇文章主要介绍了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 *Node    prev *Node    val int      key string}type AllOne struct {    head *Node    tail *Node    m 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.tail    ao.tail.prev=ao.head    return 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.next        if next==this.tail || next.val>=n.val{            return        }else{             next.prev=n.prev             n.prev.next=next                        for next.next!=this.tail && next.next.val<n.val{                next=next.next            }                                   n.next=next.next            n.prev=next                        next.next.prev=n            next.next=n        }    }else{        n:=&Node{            val:1,            key:key,            prev:this.head,            next:this.head.next,        }        this.head.next.prev=n        this.head.next=n                this.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.prev             prev.next=n.next             n.next.prev=prev                        for prev.prev!=this.head && prev.prev.val>n.val{                prev=prev.prev            }                        n.prev=prev.prev            n.next=prev                        prev.prev.next=n            prev.prev=n        }    }else{        n.prev.next=n.next        n.next.prev=n.prev        delete(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) 的数据结构”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!

golang刷leetcode技巧之如何实现全 O(1) 的数据结构

相关阅读