[Swift]LeetCode432.全O(1)的数据结构|AllO`oneDataStructure

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Implement a data structure supporting the following operations:

Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "".
GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string "".

Challenge: Perform all these in O(1) time complexity.

实现一个数据结构支持以下操作：

Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否者使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串""。
GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。

挑战：以 O(1) 的时间复杂度实现所有操作。

Runtime: 192 ms

Memory Usage: 20.9 MB

 1 class AllOne {
 2     var obj:[String:Int]
 3     /** Initialize your data structure here. */
 4     init() {
 5         self.obj = [String:Int]()        
 6     }
 7     
 8     /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
 9     func inc(_ key: String) {
10         if obj[key] != nil
11         {
12             obj[key,default:0] += 1
13         }
14         else
15         {
16             obj[key] = 1
17         }
18         
19     }
20     
21     /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
22     func dec(_ key: String) {
23         if  obj[key] != nil
24         {
25             obj[key,default:0] -= 1
26         }
27         
28         if obj[key] == 0
29         {
30             obj[key] = nil
31         }
32         
33     }
34     
35     /** Returns one of the keys with maximal value. */
36     func getMaxKey() -> String {
37         var val:Int = -1
38         var key:String = String()
39         
40         for (keys,vals) in obj
41         {
42             if vals > val
43             {
44                 val = vals
45                 key = keys
46             }
47         }
48         return key
49     }
50     
51     /** Returns one of the keys with Minimal value. */
52     func getMinKey() -> String {
53         var val:Int = Int.max
54         var key:String = String()
55          
56         for (keys,vals) in obj
57         {
58             if vals < val
59             {
60                 val = vals
61                 key = keys
62             }
63         }
64         return key
65     }
66 }
67 
68 /**
69  * Your AllOne object will be instantiated and called as such:
70  * let obj = AllOne()
71  * obj.inc(key)
72  * obj.dec(key)
73  * let ret_3: String = obj.getMaxKey()
74  * let ret_4: String = obj.getMinKey()
75  */

192ms

  1 class ListNode {
  2     var val: Int
  3     var key: String
  4     var prev: ListNode?
  5     var next: ListNode?
  6     
  7     init(_ key: String, _ val: Int) {
  8         self.key = key
  9         self.val = val
 10         self.prev = nil
 11         self.next = nil
 12     }
 13 }
 14 
 15 class AllOne {
 16     var head: ListNode = ListNode("", Int.max)
 17     var tail: ListNode = ListNode("", Int.min)
 18     var map: [String: ListNode] = [:]
 19     
 20     init() {
 21         head.next = tail
 22         tail.prev = head
 23     }
 24     
 25     func inc(_ key: String) {
 26         if let node = map[key] {
 27             node.val += 1
 28             moveForward(node)
 29         }
 30         else {
 31             let node = ListNode(key, 1)
 32             map[key] = node
 33             
 34             addNode(node)
 35         }
 36     }
 37     
 38     func dec(_ key: String) {
 39         if let node = map[key] {
 40             if node.val == 1 {
 41                 removeNode(node)
 42                 map.removeValue(forKey: key)
 43             }
 44             else {
 45                 node.val -= 1
 46                 moveBackward(node)
 47             }
 48         }
 49     }
 50     
 51     func getMaxKey() -> String {
 52         return head.next!.key
 53     }
 54     
 55     func getMinKey() -> String {
 56         return tail.prev!.key
 57     }
 58     
 59     private func moveForward(_ node: ListNode) {
 60         var insertNode = node.prev
 61         
 62         var shouldMove = false
 63         while insertNode != nil && insertNode!.val < node.val {
 64             insertNode = insertNode?.prev
 65             shouldMove = true
 66         }
 67         
 68         guard shouldMove else {
 69             return
 70         }
 71         
 72         //remove node
 73         node.prev?.next = node.next
 74         node.next?.prev = node.prev
 75         
 76         //insert
 77         node.next = insertNode?.next
 78         insertNode?.next?.prev = node
 79         
 80         insertNode?.next = node
 81         node.prev = insertNode
 82     }
 83     
 84     private func moveBackward(_ node: ListNode) {
 85         var insertNode = node.next
 86         
 87         var shouldMove = false
 88         while insertNode != nil && insertNode!.val > node.val{
 89             insertNode = insertNode?.next
 90             shouldMove = true
 91         }
 92         
 93         guard shouldMove else {
 94             return
 95         }
 96         
 97         //remove node
 98         node.prev?.next = node.next
 99         node.next?.prev = node.prev
100         
101         //insert
102         insertNode?.prev?.next = node
103         node.prev = insertNode?.prev
104         
105         insertNode?.prev = node
106         node.next = insertNode
107     }
108     
109     private func addNode(_ node: ListNode) {
110         let prevNode = tail.prev
111         
112         prevNode?.next = node
113         node.prev = prevNode
114         
115         node.next = tail
116         tail.prev = node
117     }
118     
119     private func removeNode(_ node: ListNode) {
120         node.prev?.next = node.next
121         node.next?.prev = node.prev
122         
123         node.next = nil
124         node.prev = nil
125     }
126 }
127 
128 /**
129  * Your AllOne object will be instantiated and called as such:
130  * let obj = AllOne()
131  * obj.inc(key)
132  * obj.dec(key)
133  * let ret_3: String = obj.getMaxKey()
134  * let ret_4: String = obj.getMinKey()
135  */

212ms

  1 class AllOne {
  2     class Node {
  3         var prev: Node?
  4         var next: Node?
  5         var value: Int
  6         var keys: Set<String>
  7                 
  8         init(_ key: String, _ value: Int) {
  9             self.prev = nil
 10             self.next = nil
 11             self.value = value
 12             self.keys = Set<String>()
 13             keys.insert(key)
 14         }
 15     }
 16     
 17     var head: Node?
 18     var tail: Node?
 19     var map: [String : Node]
 20     
 21     /** Initialize your data structure here. */
 22     init() {
 23         self.head = nil
 24         self.tail = nil
 25         self.map = [:]
 26     }
 27     
 28     /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
 29     func inc(_ key: String) {
 30         // modify the old node
 31         if let old_home = map[key] {
 32             let new_home: Node
 33             if let n = old_home.next {
 34                 // upper neighbor exists and is new_home
 35                 if n.value == old_home.value + 1 {
 36                     new_home = n
 37                     new_home.keys.insert(key)
 38                 } else {
 39                     // upper neighbor exists but is not new_home, so create and make room
 40                     new_home = Node(key, old_home.value + 1)
 41                     new_home.next = n
 42                     new_home.prev = old_home
 43                     
 44                     old_home.next = new_home
 45                     n.prev = new_home
 46                 }
 47             } else {
 48                 // old_home was head, so update head and create node
 49                 new_home = Node(key, old_home.value + 1)
 50                 head?.next = new_home
 51                 new_home.prev = head
 52                 head = new_home
 53             }
 54             
 55             map[key] = new_home
 56             old_home.keys.remove(key)
 57             
 58             // If the old_home needs to be removed
 59             if old_home.keys.count == 0 {
 60                 if let t = tail, old_home.value == t.value {
 61                     tail = tail?.next
 62                     tail?.prev = nil
 63                 } else {
 64                     old_home.prev?.next = old_home.next
 65                     old_home.next?.prev = old_home.prev
 66                 }
 67             }
 68             
 69         } else {
 70             // Key not in map
 71             if let old_tail = tail {
 72                 if old_tail.value == 1 {
 73                     old_tail.keys.insert(key)
 74                     map[key] = old_tail
 75                 } else {
 76                     let n = Node(key, 1)
 77                     old_tail.prev = n
 78                     n.next = old_tail
 79                     tail = n
 80                     map[key] = n
 81                 }
 82             } else {
 83                 let n = Node(key, 1)
 84                 tail = n
 85                 head = n
 86                 map[key] = n
 87             }
 88         }
 89     }
 90     
 91     /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
 92     func dec(_ key: String) {
 93         guard let old_home = map[key] else {
 94             return
 95         }
 96 
 97         if old_home.value == 1 {
 98             map.removeValue(forKey: key)
 99         } else {
100             let new_home: Node
101             if let n = old_home.prev {
102                 if n.value == old_home.value - 1 {
103                     // left neighbor both exists and is new_home
104                     new_home = n
105                     new_home.keys.insert(key)
106                 } else {
107                     // left neighbor exists but is not new_home
108                     new_home = Node(key, old_home.value - 1)
109                     old_home.prev?.next = new_home
110                     new_home.prev = old_home.prev
111                     old_home.prev = new_home
112                     new_home.next = old_home
113                 }
114             } else {
115                 // old_home is tail and not 1
116                 new_home = Node(key, old_home.value - 1)
117                 new_home.next = tail
118                 tail?.prev = new_home
119                 tail = new_home
120             }
121             map[key] = new_home
122         }
123         old_home.keys.remove(key)
124 
125         // If the old_home needs to be removed
126         if old_home.keys.count == 0 {
127             if let t = tail, old_home.value == t.value {
128                 tail = tail?.next
129                 tail?.prev = nil
130             } else if let h = head, h.value == old_home.value {
131                 head = head?.prev
132                 head?.next = nil
133             } else {
134                 old_home.prev?.next = old_home.next
135                 old_home.next?.prev = old_home.prev
136             }
137         }
138 
139     }
140     
141     /** Returns one of the keys with maximal value. */
142     func getMaxKey() -> String {
143         return head?.keys.first ?? ""
144     }
145     
146     /** Returns one of the keys with Minimal value. */
147     func getMinKey() -> String {
148         return tail?.keys.first ?? ""
149         
150     }
151 }

216ms

  1 class Node {
  2     private(set) var val: Int
  3     var keys = Set<String>()
  4     var prev: Node?
  5     var next: Node?
  6     init(_ val: Int) {
  7         self.val = val
  8 }
  9 }
 10 class AllOne {
 11     private var head: Node?
 12     private var tail: Node?
 13     private var keyToNodeMap = [String: Node]()
 14     private var valToNodeMap = [Int: Node]()
 15     /** Initialize your data structure here. */
 16     init() {
 17         
 18     }
 19     
 20     /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
 21     func inc(_ key: String) {
 22         let node = keyToNodeMap[key]
 23         let val = node?.val ?? 0
 24         var newNode: Node
 25         if let next = node?.next,
 26 next.val == val + 1 {
 27             newNode = next
 28 } else {
 29     newNode = valToNodeMap[val + 1] ?? Node(val + 1)
 30 }
 31 
 32 node?.keys.remove(key)
 33 newNode.keys.insert(key)
 34 keyToNodeMap[key] = newNode
 35 valToNodeMap[val + 1] = newNode
 36 
 37 if node == nil && newNode !== head {
 38     add(newNode, before: head)
 39 } else {
 40 add(newNode, after: node)
 41 }
 42 if let n = node, n.keys.count == 0 {
 43     remove(n)
 44 }
 45     }
 46     
 47     /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
 48     func dec(_ key: String) {
 49          guard let node = keyToNodeMap[key] else { return }
 50         let val = node.val
 51         var newNode: Node?
 52         if let prev = node.prev,
 53 prev.val == val - 1 {
 54             newNode = prev
 55 } else if val - 1 > 0 {
 56     newNode = valToNodeMap[val + 1] ?? Node(val - 1)
 57 }
 58 
 59 node.keys.remove(key)
 60 newNode?.keys.insert(key)
 61         keyToNodeMap[key] = newNode
 62         valToNodeMap[val - 1] = newNode
 63 
 64 if let nn = newNode {
 65     add(nn, before: node)
 66 }
 67 if node.keys.count == 0 {
 68     remove(node)
 69 }
 70     }
 71 
 72     private func remove(_ node: Node?) {
 73         guard let node = node else { return }
 74         node.prev?.next = node.next
 75         node.next?.prev = node.prev
 76         if head === node {
 77             head = node.next
 78 }
 79 if tail === node {
 80     tail = node.prev
 81 }
 82 }
 83 
 84     private func add(_ node: Node, before nextNode: Node?) {
 85         if nextNode?.prev !== node {
 86         nextNode?.prev?.next = node
 87         node.prev = nextNode?.prev
 88         }
 89         nextNode?.prev = node
 90         node.next = nextNode
 
                       
                    
                     
                      



鲜花




握手




雷人




路过




鸡蛋