[705] Design HashSet | LeetCode Easy

yoongyumยท2022๋…„ 4์›” 22์ผ
0

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๐Ÿงฉ

๋ชฉ๋ก ๋ณด๊ธฐ
17/47
post-thumbnail

๐Ÿ”Ž๋ฌธ์ œ์„ค๋ช…

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

Implement MyHashSet class:

  • void add(key) Inserts the value key into the HashSet.
  • bool contains(key) Returns whether the value key exists in the HashSet or not.
  • void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

Example 1

Input
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]

Output
[null, null, null, true, false, null, true, null, false]

Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // return False, (already removed)

์ œํ•œ์‚ฌํ•ญ

  • 0 โ‰ค key โ‰ค 10610^6
  • At most 104 calls will be made to add, remove, and contains.


๐ŸงŠ ํŒŒ์ด์ฌ ์ฝ”๋“œ

class MyHashSet:
    
    def __init__(self):
        self.hs = set()

    def add(self, key: int) -> None:
        self.hs.add(key)

    def remove(self, key: int) -> None:
        self.hs.discard(key)

    def contains(self, key: int) -> bool:
        return key in self.hs 

์‹œ๊ฐ„๋ณต์žก๋„ O(1)

๐Ÿน ๋‹ค๋ฅธํ’€์ด

class MyHashSet:
    def __init__(self):
        self.hs = []
    
    def add(self, key: int) -> None:
        if not self.contains(key):
            self.hs.append(key)
    
    def remove(self, key: int) -> None:
        if self.contains(key):
            self.hs.remove(key)
    
    def contains(self, key: int) -> bool:
        return key in self.hs

์‹œ๊ฐ„๋ณต์žก๋„ O(n)

๐Ÿธ ๋˜๋‹ค๋ฅธํ’€์ด

class MyHashSet:
    BUCKET_SIZE = 256  

    def __init__(self):
        self.hs = [[] for _ in range(self.BUCKET_SIZE)]  

    def add(self, key: int) -> None:
        if not self.contains(key):
            self.curr.append(key)  

    def remove(self, key: int) -> None:
        if self.contains(key):
            self.curr.remove(key)  

    def contains(self, key: int) -> bool:
        self.curr = self.hs[key%self.BUCKET_SIZE]  
        return key in self.curr  

์‹œ๊ฐ„๋ณต์žก๋„ O(BUCKET_SIZE)

0๊ฐœ์˜ ๋Œ“๊ธ€