# LeetCode Easy 705. Design HashSet

tags: leetcode

学科の研究室の選抜(？)の第一段階に自分の名前がなくて萎えています．

研究室に顔を出しても入れなかったらどうしようか…と思い鬱．とりあえず実装をします．

問題

• Explore
• Problems

アイデア

組み込みライブラリを使わずにHashSetを設計せよという問題．以下の関数を含む必要がある．

• add(value): HaseSetに値を挿入する．
• contains(value): HashSetに値が存在するかどうかを返す．
• remove(value): HashSetから値を取り除く．もし，HashSetに値がなければ何もしない．

どの程度の実装にすれば良いのかよくわからず…

解法1(お手軽)

雑過ぎる解法として1次元のboolean配列で管理するという方法があります．

この問題の値の範囲が狭いことからこの解法でも可能です(おそらくもっと大きくした方が問題として良いです)．

計算量

値の範囲が[0, N)とします．

• 時間計算量
  • コンストラクタは$O(N)$で，他は$O(1)$
• 空間計算量
  • コンストラクタは$O(N)$で，他は$O(1)$

値の範囲が広くなると空間計算量が非常に大きくなるので実際にこの方法で実装されることはないはず？

C++

class MyHashSet {
private:
  vector<bool> hashSet;
public:
    /** Initialize your data structure here. */
    MyHashSet(): hashSet(vector<bool>(1000001)) {}
    
    void add(int key) {
      hashSet[key] = true;
    }
    
    void remove(int key) {
      hashSet[key] = false;
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
      return hashSet[key];
    }
};

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

解法2(二次元配列)

実装がバグっているので後日上げるかも知れません(これ何回目だ)．