# O(1), With Explanation, Double linked-list with sentinel & hash

• Double linked-list with sentinel & hash implementation

The principle is maintain a double linked-list, and pushes all element with same
value n into a single hash bucket(n).

bucket(1) <-> bucket(2) <-> bucket(5) <-> bucket(7)


INC operation, O(1), if key is exists and it's value is n, just move the key to the bucket(n+1). Otherwise, push it into bucket(1).

DEC operation, O(1), if key is exists and it's value is n, just move the key to the bucket(n-1). Otherwise, do nothing.

MIN operation, O(1), random get a key from head node.

MAX operation, O(1), random get a key from tail node.

type Node struct {
prev  *Node
next  *Node
keys  map[string]bool
value int
}

type AllOne struct {
nil_node *Node
nodemap  map[string]*Node
}

/** Initialize your data structure here. */
func Constructor() AllOne {
nil_node := &Node{
prev:  nil,
next:  nil,
keys:  make(map[string]bool),
value: 0,
}
nil_node.next = nil_node
nil_node.prev = nil_node
return AllOne{
nil_node: nil_node,
nodemap:  make(map[string]*Node),
}
}

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
func (this *AllOne) Inc(key string) {
n := this.nodemap[key]
if n != nil {
next := n.next
delete(n.keys, key)

if next.value == n.value+1 {
next.keys[key] = true
this.nodemap[key] = next
} else {
o := &Node{
prev:  nil,
next:  nil,
keys:  make(map[string]bool),
value: n.value + 1,
}

n.next = o
o.prev = n
o.next = next
next.prev = o

o.keys[key] = true
this.nodemap[key] = o
}

if len(n.keys) == 0 {
// delete node n
n.prev.next = n.next
n.next.prev = n.prev
}
} else {
} else {
o := &Node{
prev:  nil,
next:  nil,
keys:  make(map[string]bool),
value: 1,
}
o.next = this.nil_node.next
this.nil_node.next.prev = o
this.nil_node.next = o
o.prev = this.nil_node

o.keys[key] = true
this.nodemap[key] = o
}
}
}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
func (this *AllOne) Dec(key string) {
n := this.nodemap[key]
if n != nil {
prev := n.prev
delete(n.keys, key)

if n.value == 1 {
delete(this.nodemap, key)
} else {
if prev.value == n.value-1 {
prev.keys[key] = true
this.nodemap[key] = prev
} else {
o := &Node{
prev:  nil,
next:  nil,
keys:  make(map[string]bool),
value: n.value - 1,
}

prev.next = o
o.prev = prev
o.next = n
n.prev = o

o.keys[key] = true
this.nodemap[key] = o
}
}

if len(n.keys) == 0 {
// delete node n
n.prev.next = n.next
n.next.prev = n.prev
}
}
}

/** Returns one of the keys with maximal value. */
func (this *AllOne) GetMaxKey() string {
for key := range this.nil_node.prev.keys {
return key
}
return ""
}

/** Returns one of the keys with Minimal value. */
func (this *AllOne) GetMinKey() string {
for key := range this.nil_node.next.keys {
return key
}
return ""
}


Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.