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