432. All O`one Data Structure
請實作一個資料結構
包含以下功能
AllOne() : 初始化資料結構
inc(string key) : 將key的次數+1，如果本來沒有key就將其插入
dec(string key) : 將key的次數-1，如果次數變為0就把key移除
getMaxKey() : 回傳最大次數的key，如果有多個則會傳任一個，若沒有任何key回傳-1
getMinKey() : 回傳最小次數的key，如果有多個則回傳任一個，若沒有任何key回傳-1
以上操作都要在O(1)時間複雜度內
思路:
用雙向鏈結串列，該鏈結串列的value是目前出現字串的次數
且由小排到大
假設出現過的字串有
EX : A、A、A、A、B、B、B、B、C、C、D
則鏈結串列會是 1<->2<->4
建立3個hash table
table1 = map[字串]出現次數
table2 = map[次數]雙向鏈結串列的node
table3 = map[次數]map[字串][是否存在]
要回傳最小時，就去找雙向鏈結串列的head，看次數是多少，接著隨便回傳一個相同次數的字串
要回傳最大時，就去找雙向鏈結串列的tail
就按照題目去維護雙向鏈結串列和3個hash table
就可以實做出來了
golang code :
type doubly_linknode struct {
val int
prev *doubly_linknode
next *doubly_linknode
}
type AllOne struct {
head *doubly_linknode
tail *doubly_linknode
map_string_cnt map[string]int
map_cnt_linkedlist map[int]*doubly_linknode
map_cnt_string_struct map[int]map[string]struct{}
}
func Constructor() AllOne {
res := AllOne{}
res.map_cnt_linkedlist = make(map[int]*doubly_linknode)
res.map_cnt_string_struct = make(map[int]map[string]struct{})
res.map_string_cnt = make(map[string]int)
res.head = &doubly_linknode{-1, nil, nil}
res.tail = &doubly_linknode{math.MaxInt32, res.head, nil}
res.head.next = res.tail
res.map_cnt_string_struct[-1] = make(map[string]struct{})
res.map_cnt_string_struct[-1][""] = struct{}{}
res.map_cnt_string_struct[math.MaxInt32] = make(map[string]struct{})
res.map_cnt_string_struct[math.MaxInt32][""] = struct{}{}
return res
}
func (this *AllOne) Inc(key string) {
if _, ok := this.map_string_cnt[key]; !ok {
if _, ok1 := this.map_cnt_linkedlist[1]; !ok1 {
newnode := &doubly_linknode{1, nil, nil}
newnode.prev = this.head
newnode.next = this.head.next
this.head.next = newnode
newnode.next.prev = newnode
this.map_cnt_linkedlist[1] = newnode
}
this.map_string_cnt[key] = 1
if _, ok2 := this.map_cnt_string_struct[1]; !ok2 {
this.map_cnt_string_struct[1] = make(map[string]struct{})
}
this.map_cnt_string_struct[1][key] = struct{}{}
} else {
old_idx := this.map_string_cnt[key]
this.map_string_cnt[key]++
new_idx := this.map_string_cnt[key]
prev_node := this.map_cnt_linkedlist[old_idx].prev
next_node := this.map_cnt_linkedlist[old_idx].next
if len(this.map_cnt_string_struct[old_idx]) == 1 {
delete(this.map_cnt_string_struct, old_idx)
prev_node.next = next_node
next_node.prev = prev_node
delete(this.map_cnt_linkedlist, old_idx)
} else {
delete(this.map_cnt_string_struct[old_idx], key)
}
if _, ok1 := this.map_cnt_string_struct[new_idx]; !ok1 {
newnode := &doubly_linknode{new_idx, nil, nil}
this.map_cnt_linkedlist[new_idx] = newnode
if _, exist := this.map_cnt_linkedlist[old_idx]; !exist {
newnode.next = next_node
next_node.prev = newnode
newnode.prev = prev_node
prev_node.next = newnode
} else {
newnode.next = next_node
next_node.prev = newnode
newnode.prev = this.map_cnt_linkedlist[old_idx]
this.map_cnt_linkedlist[old_idx].next = newnode
}
}
if _, ok2 := this.map_cnt_string_struct[new_idx]; !ok2 {
this.map_cnt_string_struct[new_idx] = make(map[string]struct{})
}
this.map_cnt_string_struct[new_idx][key] = struct{}{}
}
}
func (this *AllOne) Dec(key string) {
old_idx := this.map_string_cnt[key]
this.map_string_cnt[key]