705. 해시세트 설계

705. 해시세트 설계



설명



내장된 해시 테이블 라이브러리를 사용하지 않고 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 , removecontains 으로 이루어집니다.



  • 솔루션



    솔루션 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);
     */
    


    복잡성


  • 시간: O(n)
  • 공간: O(n)
  • 좋은 웹페이지 즐겨찾기