How to realize the data structure of all O (1) with the skill of golang browsing leetcode
This article mainly introduces the golang brush leetcode skills how to achieve full O (1) data structure, has a certain reference value, interested friends can refer to, I hope you can learn a lot after reading this article, the following let Xiaobian with you to understand.
Please implement a data structure that supports the following operations:
Inc (key)-insert a new key with a value of 1. Or add one to an existing key to ensure that the key is not an empty string.
Dec (key)-if the value of the key is 1, remove it from the data structure. Otherwise, subtract one of the existing key values. If the key doesn't exist, the function doesn't do anything. Key guarantees that the string is not empty.
GetMaxKey ()-returns any one of the highest values in the key. If no element exists, an empty string "" is returned.
GetMinKey ()-returns any of the lowest values in the key. If no element exists, an empty string "" is returned.
Challenge:
Can you implement all operations with O (1) time complexity?
Problem-solving ideas
1, this is a variant of lru, in the form of hash+ ordered double linked list
2. Remove the current node from the linked list every time inc and dec
3, and then find the appropriate location to insert
4. Note that after inc, the values of the subsequent continuous constants are equal and require special handling.
5 similar to the dec
Code implementation
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 with value 1. Or increments an existing key by 1. * / func (this * AllOne) Inc (key string) {if n 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.nextDesigthis.tail & & next.next.val
