LeetCode-705

题目

705. 设计哈希集合

结果

代码

大二的数据结构课上，听了听就觉得自己很懂了，但是写起来还是有很多细节要考虑：比如数组应该在什么时候扩容，除法运算时除数应该选多少，还有扩容问题。

type MyHashSet struct {
   arr       [][]int
   threshold int
   cnt       int // how many elements do we have
}

/** Initialize your data structure here. */
func Constructor() MyHashSet {
   return MyHashSet{
      arr:       make([][]int, 16, 16),
      threshold: 16,
   }
}

// insertion sort
func (s *MyHashSet) Add(key int) {
   if s.Contains(key) {
      return
   }
   s.resize()
   idx := key % len(s.arr)
   s.arr[idx] = append(s.arr[idx], key)
   s.cnt++
}

func (s *MyHashSet) Remove(key int) {
   if !s.Contains(key) {
      return
   }
   idx := key % len(s.arr)
   for i, v := range s.arr[idx] {
      if v == key {
         s.arr[idx] = remove(s.arr[idx], i)
         return
      }
   }
}

/** Returns true if this set contains the specified element */
func (s *MyHashSet) Contains(key int) bool {
   idx := key % len(s.arr)
   for _, v := range s.arr[idx] {
      if key == v {
         return true
      }
   }
   return false
}

func (s *MyHashSet) resize() {
   if s.cnt <= s.threshold {
      return
   }
   // TODO: resize
   _s := MyHashSet{
      arr:       make([][]int, s.threshold*4, s.threshold*4),
      threshold: s.threshold * 2,
      cnt:       s.cnt,
   }
   for _, v1 := range s.arr {
      for _, v2 := range v1 {
         _s.Add(v2)
      }
   }
   s.arr = _s.arr
   s.threshold = _s.threshold
   s.cnt = _s.cnt
}

/*
func remove(nums []int, i int) []int {
   return append(nums[:i], nums[i+1:]...)
}
*/

func remove(s []int, i int) []int {
   s[len(s)-1], s[i] = s[i], s[len(s)-1]
   return s[:len(s)-1]
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(key);
 * obj.Remove(key);
 * param_3 := obj.Contains(key);
 */

删除slice中的元素

Order matters

If you want to keep your array ordered, you have to shift all of the elements at the right of the deleting index by one to the left. Hopefully, this can be done easily in Golang:

func remove(slice []int, s int) []int {
    return append(slice[:s], slice[s+1:]...)
}

However, this is inefficient because you may end up with moving all of the elements, which is costy.

Order is not important

If you do not care about ordering, you have the much faster possibility to swap the element to delete with the one at the end of the slice and then return the n-1 first elements:

func remove(s []int, i int) []int {
    s[len(s)-1], s[i] = s[i], s[len(s)-1]
    return s[:len(s)-1]
}

我这种HashSet的实现，拉链中的元素顺序不重要，因此后者是最佳选择。

复杂度

时间复杂度：O（1），不论是查找还是删除

空间复杂度：O（n），需要两倍于元素数量的空间