[Swift]LeetCode705.设计哈希集合|DesignHashSet

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

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

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

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

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

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

Design a HashSet without using any built-in hash table libraries.

To be specific, your design should include these functions:

add(value): Insert a value into the HashSet.
contains(value) : Return whether the value exists in the HashSet or not.
remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.

Example:

MyHashSet hashSet = new MyHashSet();
hashSet.add(1);         
hashSet.add(2);         
hashSet.contains(1);    // returns true
hashSet.contains(3);    // returns false (not found)
hashSet.add(2);          
hashSet.contains(2);    // returns true
hashSet.remove(2);          
hashSet.contains(2);    // returns false (already removed)

Note:

All values will be in the range of [0, 1000000].
The number of operations will be in the range of [1, 10000].
Please do not use the built-in HashSet library.

不使用任何内建的哈希表库设计一个哈希集合

具体地说，你的设计应该包含以下的功能

add(value)：向哈希集合中插入一个值。
contains(value) ：返回哈希集合中是否存在这个值。
remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例:

MyHashSet hashSet = new MyHashSet();
hashSet.add(1);         
hashSet.add(2);         
hashSet.contains(1);    // 返回 true
hashSet.contains(3);    // 返回 false (未找到)
hashSet.add(2);          
hashSet.contains(2);    // 返回 true
hashSet.remove(2);          
hashSet.contains(2);    // 返回  false (已经被删除)

注意：

所有的值都在 [1, 1000000]的范围内。
操作的总数目在[1, 10000]范围内。
不要使用内建的哈希集合库。

456ms

 1 class MyHashSet {
 2 
 3     var map = [Bool](repeating: false, count: 1000000)
 4     
 5     /** Initialize your data structure here. */
 6     init() {
 7         
 8     }
 9     
10     func add(_ key: Int) {
11         map[key] = true
12     }
13     
14     func remove(_ key: Int) {
15         map[key] = false
16     }
17     
18     /** Returns true if this set contains the specified element */
19     func contains(_ key: Int) -> Bool {
20         return map[key]
21     }
22 }
23 
24 /**
25  * Your MyHashSet object will be instantiated and called as such:
26  * let obj = MyHashSet()
27  * obj.add(key)
28  * obj.remove(key)
29  * let ret_3: Bool = obj.contains(key)
30  */

Runtime: 432 ms

Memory Usage: 20.8 MB

 1 class LinkedNode {
 2     var next: LinkedNode?
 3     var val: Int
 4     
 5     init(_ val: Int) {
 6         self.val = val
 7     }
 8 }
 9 
10 class MyHashSet {
11     
12     private var nums: [LinkedNode?]
13 
14     /** Initialize your data structure here. */
15     init() {
16         nums = Array(repeating: nil, count: 10000)
17     }
18     
19     func add(_ key: Int) {
20         let index = hash(key)
21         if let node = nums[index] {
22             var next: LinkedNode? = node
23             var pre: LinkedNode? = nil
24             while next != nil {
25                 if next!.val == key {
26                     return
27                 }
28             
29                 pre = next
30                 next = next?.next
31             }
32             
33             pre?.next = LinkedNode(key)
34         } else {
35             nums[index] = LinkedNode(key)
36         }
37     }
38     
39     func remove(_ key: Int) {
40         let index = hash(key)
41         guard let node = nums[index] else {
42             return
43         }
44         
45         var next: LinkedNode? = node
46         var pre: LinkedNode? = nil
47         while next != nil {
48             if next!.val == key {
49                 if pre != nil {
50                     pre?.next = next!.next
51                 } else {
52                     nums[index] = next!.next
53                 }
54                 break
55             }
56             
57             pre = next
58             next = next?.next
59         }
60     }
61     
62     /** Returns true if this set contains the specified element */
63     func contains(_ key: Int) -> Bool {
64         let index = hash(key)
65         guard let node = nums[index] else {
66             return false
67         }
68         
69         var next: LinkedNode? = node
70         while next != nil {
71             if next!.val == key {
72                 return true
73             }
74             
75             next = next?.next
76         }
77         
78         return false
79     }
80     
81     func hash(_ key: Int) -> Int {
82         return key % 10000
83     }
84     
85 }
86 
87 /**
88  * Your MyHashSet object will be instantiated and called as such:
89  * let obj = MyHashSet()
90  * obj.add(key)
91  * obj.remove(key)
92  * let ret_3: Bool = obj.contains(key)
93  */

460ms

 1 class MyHashSet {
 2     
 3     var buckets: [[Int]]
 4     let MAX_LENGTH = 10000
 5     /** Initialize your data structure here. */
 6     init() {
 7         buckets = Array(repeating:[Int](), count: MAX_LENGTH)
 8     }
 9     
10     private func getIndex(_ key: Int) -> Int {
11         return key % MAX_LENGTH
12     }
13     
14     func add(_ key: Int) {
15       if !self.contains(key) {
16         buckets[getIndex(key)].append(key)    
17       }
18       
19     }
20     
21     func remove(_ key: Int) {
22        let bucketIndex = getIndex(key)
23         for i in (0..<buckets[bucketIndex].count).reversed() {
24             if buckets[bucketIndex][i] == key {
25                 buckets[bucketIndex].remove(at: i)
26             }
27         }
28     }
29     
30     /** Returns true if this set contains the specified element */
31     func contains(_ key: Int) -> Bool {
32         let bucketIndex = getIndex(key)
33         for item in buckets[bucketIndex] {
34             if item == key {
35                 return true
36             }
37         }
38         return false
39     }
40 }

488ms

 1 class MyHashSet {
 2     var hash = [[Int]](repeating:[Int](), count: 1000)
 3     /** Initialize your data structure here. */
 4     init() {
 5         
 6     }
 7     
 8     func add(_ key: Int) {
 9         let hashKey = key % 1000
10         if !contains(key) {
11             hash[hashKey].append(key)
12         }
13     }
14     
15     func remove(_ key: Int) {
16         let hashKey = key % 1000
17         hash[hashKey] = hash[hashKey].filter { $0 != key }
18     }
19     
20     /** Returns true if this set contains the specified element */
21     func contains(_ key: Int) -> Bool {
22         let hashKey = key % 1000
23         if !hash[hashKey].contains(key) {
24             return false
25         } else {
26             return true
27         }
28     }
29 }

508ms

 1 class MyHashSet {
 2     
 3     private var array = [Bool]()
 4 
 5     /** Initialize your data structure here. */
 6     init() {
 7         
 8     }
 9     
10     func add(_ key: Int) {
11         if array.count <= key {
12             array += Array(repeating: false, count: key - array.count + 1)
13         }
14         
15         array[key] = true
16     }
17     
18     func remove(_ key: Int) {
19         if array.count <= key {
20             return
21         }
22         array[key] = false
23     }
24     
25     /** Returns true if this set contains the specified element */
26     func contains(_ key: Int) -> Bool {
27         if array.count <= key {
28             return false
29         }
30         return array[key]
31     }
32 }

512ms

 1 class MyHashSet {
 2 
 3     var hashset: [ Int ]
 4 
 5     /** Initialize your data structure here. */
 6     init() {
 7         hashset = [ Int ](repeating: 0, count: 1000000 >> 6) // 64-bit
 8     }
 9     
10     func offset(_ key: Int) -> (Int, Int) {
11         let byte = key >> 6
12         let bit = 1 << (key % 64)
13         return (byte, bit)
14     }
15     
16     func add(_ key: Int) {
17         let (byte, bit) = offset(key)
18         hashset[byte] |= bit
19     }
20     
21     func remove(_ key: Int) {
22         let (byte, bit) = offset(key)
23         hashset[byte] &= (bit ^ -1)
24     }
25     
26     /** Returns true if this set contains the specified element */
27     func contains(_ key: Int) -> Bool {
28         let (byte, bit) = offset(key)
29         return hashset[byte] & bit != 0
30     }
31 }

516ms

 1 class MyHashSet {
 2     
 3     private var array = [Bool]()
 4 
 5     /** Initialize your data structure here. */
 6     init() {
 7         
 8     }
 9     
10     func add(_ key: Int) {
11         if array.count <= key {
12             array += Array(repeating: false, count: key - array.count + 1)
13         }
14         
15         array[key] = true
16     }
17     
18     func remove(_ key: Int) {
19         if array.count <= key {
20             return
21         }
22         array[key] = false
23     }
24     
25     /** Returns true if this set contains the specified element */
26     func contains(_ key: Int) -> Bool {
27         if array.count <= key {
28             return false
29         }
30         return array[key]
31     }
32 }

684ms

 1 class LinkedNode {
 2     var next: LinkedNode?
 3     var val: Int
 4     
 5     init(_ val: Int) {
 6         self.val = val
 7     }
 8 }
 9 
10 class MyHashSet {
11     
12     private var nodes: [LinkedNode?]
13 
14     /** Initialize your data structure here. */
15     init() {
16         nodes = Array(repeating: nil, count: 10000)
17     }
18     
19     func add(_ key: Int) {
20         let index = hash(key)
21         guard let node = nodes[index] else {
22             nodes[index] = LinkedNode(key)
23             return
24         }
25         
26         var next: LinkedNode? = node
27         var pre: LinkedNode? = nil
28         while next != nil, next!.val != key {
29             pre = next
30             next = next?.next
31         }
32         
33         if next == nil {
34             pre?.next = LinkedNode(key)
35         }
36     }
37     
38     func remove(_ key: Int) {
39         let index = hash(key)
40         guard let node = nodes[index] else {
41             return
42         }
43         
44         var next: LinkedNode? = node
45         var pre: LinkedNode? = nil
46         while next != nil, next!.val != key {
47             pre = next
48             next = next?.next
49         }
50         
51         if let pre = pre {
52             pre.next = next?.next
53         } else {
54             nodes[index] = next?.next
55         }
56     }
57     
58     /** Returns true if this set contains the specified element */
59     func contains(_ key: Int) -> Bool {
60         let index = hash(key)
61         guard let node = nodes[index] else {
62             return false
63         }
64         
65         var next: LinkedNode? = node
66         while next != nil, next!.val != key {
67             next = next?.next
68         }
69         
70         return next != nil
71     }
72     
73     private func hash(_ key: Int) -> Int {
74         return key % 10000
75     }    
76 }

860ms

 1 class MyHashSet {
 2     var values: [Int]
 3     /** Initialize your data structure here. */
 4     init() {
 5         values = Array.init(repeating: -1, count: 1000000)
 6     }
 7     
 8     func add(_ key: Int) {
 9         values[key] = key
10     }
11     
12     func remove(_ key: Int) {
13         values[key] = -1
14     }
15     
16     /** Returns true if this set contains the specified element */
17     func contains(_ key: Int) -> Bool {
18         if key < values.count {
19             return values[key] != -1
20         }
21         
22         return false
23     }
24 }