705. Design HashSet

Leetcode link

解题思路

本题要求我们实现一个简单的 hashSet 的 add、contains、remove 方法

一个最简单的想法就是用一个 map 去建立所有新增进来的 key 的映射，这样就会非常简单，下面我用 JS 实现了这个思路

另一个想法就是用 N 个 “桶” 来 “分类” 一下要新增的 key，具体而言，我们用 key % N 来做分类。这样可以降低空间使用。下面我用 C++ 实现这种思路。

C++

class MyHashSet {
 private:
  // 由于题目说 key 的范围大概在 10^6，所以取个 10^2 就差不多了，当然可以随意调整
  const int BUCKET_SIZE = 100;
  vector<int> bucket[100];

 public:
  MyHashSet() {}

  void add(int key) {
    int index = key % BUCKET_SIZE;
    if (!contains(key)) {
      bucket[index].push_back(key);
    }
  }

  void remove(int key) {
    int index = key % BUCKET_SIZE;
    auto it = find(bucket[index].begin(), bucket[index].end(), key);
    if (it != bucket[index].end()) {
      bucket[index].erase(it);
    }
  }

  bool contains(int key) {
    int index = key % BUCKET_SIZE;
    if (find(bucket[index].begin(), bucket[index].end(), key) !=
        bucket[index].end()) {
      return true;
    } else {
      return false;
    }
  }
};

Javascript

var MyHashSet = function() {
    this.set = {};
};

/** 
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.add = function(key) {
    this.set[key] = key;
};

/** 
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.remove = function(key) {
    delete this.set[key];
};

/** 
 * @param {number} key
 * @return {boolean}
 */
MyHashSet.prototype.contains = function(key) {
    return key in this.set
};