LeetCode 솔루션 분류
705. Design HashSet
본문
[LeetCode 시즌 3] 2022년 4월 20일 문제입니다
[Easy] 705. Design HashSet
Design a HashSet without using any built-in hash table libraries.
Implement MyHashSet class:
void add(key)Inserts the valuekeyinto the HashSet.bool contains(key)Returns whether the valuekeyexists in the HashSet or not.void remove(key)Removes the valuekeyin the HashSet. Ifkeydoes 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)
Constraints:
0 <= key <= 106- At most
104calls will be made toadd,remove, andcontains.
태그
#LeetCode, #문제풀이, #시즌3, #easy, #Microsoft, #Array, #Hash Table, #Linked List, #Design, #Hash Function
관련자료
-
링크
댓글 3
9dea0936님의 댓글
- 익명
- 작성일
class MyHashSet:
def __init__(self):
self.hashVal = 10**6
self.hashSet = [-1] * 10**6
def add(self, key: int) -> None:
if self.hashSet[key % self.hashVal] == -1:
self.hashSet[key % self.hashVal] = key
def remove(self, key: int) -> None:
if self.hashSet[key % self.hashVal] != -1:
self.hashSet[key % self.hashVal] = -1
def contains(self, key: int) -> bool:
if self.hashSet[key % self.hashVal] == -1:
return False
else:
return True
bobkim님의 댓글
- 익명
- 작성일
Runtime: 301 ms, faster than 13.14% of C++ online submissions for Design HashSet.
Memory Usage: 39.5 MB, less than 95.69% of C++ online submissions for Design HashSet.
Memory Usage: 39.5 MB, less than 95.69% of C++ online submissions for Design HashSet.
class MyHashSet {
public:
std::vector<int> HashSet;
MyHashSet() {
}
void add(int key) {
int count = 0;
for(std::vector<int>::iterator itr=HashSet.begin();itr!=HashSet.end();itr++){
if(*itr==key){
count++;
};
};
if(count == 0){
HashSet.push_back(key);
};
}
void remove(int key) {
for(std::vector<int>::iterator itr=HashSet.begin();itr!=HashSet.end();itr++){
if(*itr == key){
HashSet.erase(itr);
return;
};
};
}
bool contains(int key) {
for(std::vector<int>::iterator itr=HashSet.begin();itr!=HashSet.end();itr++){
if(*itr == key){
return true;
};
};
return false;
}
};Coffee님의 댓글
- 익명
- 작성일
Runtime: 17 ms, faster than 81.35% of Java online submissions for Design HashSet.
Memory Usage: 49.6 MB, less than 93.16% of Java online submissions for Design HashSet.
Memory Usage: 49.6 MB, less than 93.16% of Java online submissions for Design HashSet.
class MyHashSet {
private Store[] storeArray;
private int modulo;
public MyHashSet() {
this.modulo = 999;
this.storeArray = new Store[this.modulo];
for(int i=0; i<this.modulo; i++){
this.storeArray[i] = new Store();
}
}
private int doHash(int key){
return (key % this.modulo);
}
public void add(int key) {
int storeIndex = this.doHash(key);
this.storeArray[storeIndex].insert(key);
}
public void remove(int key) {
int storeIndex = this.doHash(key);
this.storeArray[storeIndex].delete(key);
}
public boolean contains(int key) {
int storeIndex = this.doHash(key);
return this.storeArray[storeIndex].isExist(key);
}
class Store{
private LinkedList<Integer> list;
public Store() {
list = new LinkedList<Integer>();
}
public void insert(Integer key){
int index = this.list.indexOf(key);
if(index == -1){
this.list.addFirst(key);
}
}
public void delete(Integer key){
this.list.remove(key);
}
public boolean isExist(Integer key){
int index = this.list.indexOf(key);
return (index != -1);
}
}
}
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet obj = new MyHashSet();
* obj.add(key);
* obj.remove(key);
* boolean param_3 = obj.contains(key);
*/
