705. 해시세트 설계
705. 해시세트 설계
설명
내장된 해시 테이블 라이브러리를 사용하지 않고 HashSet을 설계합니다.
MyHashSet
클래스 구현:
내장된 해시 테이블 라이브러리를 사용하지 않고 HashSet을 설계합니다.
MyHashSet
클래스 구현:void add(key)
key
값을 HashSet에 삽입합니다. bool contains(key)
key
값이 HashSet에 존재하는지 여부를 반환합니다. void remove(key)
HashSet에서 key
값을 삭제합니다. key
이 HashSet에 없으면 아무것도 하지 않습니다. 예 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 <= 106
104
통화는 add
, remove
및 contains
으로 이루어집니다. 솔루션
솔루션 1
직관
암호
const int N = 113;
class MyHashSet {
private:
vector<int> mySet[N];
int find(int linkIndex, int target) {
vector<int> &link = mySet[linkIndex];
for (int i = 0; i < link.size(); i++) {
if (link[i] == target) return i;
}
return -1;
}
public:
MyHashSet() {
}
void add(int key) {
int linkIndex = key % N;
int index = find(linkIndex, key);
if (index == -1) mySet[linkIndex].push_back(key);
}
void remove(int key) {
int linkIndex = key % N;
int index = find(linkIndex, key);
if (index != -1) mySet[linkIndex].erase(mySet[linkIndex].begin() + index);
}
bool contains(int key) {
int linkIndex = key % N;
int index = find(linkIndex, key);
return index != -1;
}
};
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet* obj = new MyHashSet();
* obj->add(key);
* obj->remove(key);
* bool param_3 = obj->contains(key);
*/
복잡성
const int N = 113;
class MyHashSet {
private:
vector<int> mySet[N];
int find(int linkIndex, int target) {
vector<int> &link = mySet[linkIndex];
for (int i = 0; i < link.size(); i++) {
if (link[i] == target) return i;
}
return -1;
}
public:
MyHashSet() {
}
void add(int key) {
int linkIndex = key % N;
int index = find(linkIndex, key);
if (index == -1) mySet[linkIndex].push_back(key);
}
void remove(int key) {
int linkIndex = key % N;
int index = find(linkIndex, key);
if (index != -1) mySet[linkIndex].erase(mySet[linkIndex].begin() + index);
}
bool contains(int key) {
int linkIndex = key % N;
int index = find(linkIndex, key);
return index != -1;
}
};
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet* obj = new MyHashSet();
* obj->add(key);
* obj->remove(key);
* bool param_3 = obj->contains(key);
*/
Reference
이 문제에 관하여(705. 해시세트 설계), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/jiangwenqi/705-design-hashset-39mo텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)