美文网首页Go数据结构
(9)Go实现映射和集合

(9)Go实现映射和集合

作者: 哥斯拉啊啊啊哦 | 来源:发表于2019-04-20 19:31 被阅读1次

    映射:Map
    map 是一种无序的键值对的集合。映射的key是不重复的,因此map 最重要的一点是通过 key 来快速检索数据,key 类似于索引,指向数据的值。
    map 是一种集合,所以我们可以像迭代数组和 slice 那样迭代它。不过,map 是无序的,我们无法决定它的返回顺序,这是因为 map 是使用 hash 表来实现的,hash算法看下面:《从头到尾彻底解析Hash表算法》
    https://blog.csdn.net/fly542/article/details/6696446

    // map创建的3种方法
    1) dict := make(map[string]int)
    // 通过字面值创建
    2) dict := map[string]string{"hello": "world", "china": "best"}
    
    如果不初始化 map,那么就会创建一个 nil map, nil map 不能用来存放键值对,
    否则会报运行时错误:
    var dict map[string]string
    dict["hello"] = "world"
    
    panic: assignment to entry in nil map
    
    集合就是不同对象的无序聚集,在定义上跟映射挺像的,下面用go的映射来实现
    一种集合
    //
    type set struct {
        size int
        sets map[string]bool
    }
    
    func NewSet() *set {
        return &set{
            size: 0,
            sets: map[string]bool{},
        }
    }
    
    func (set *set) Add(str string) {
        if str == "" {
            return
        }
        v := set.sets[str]
        if !v {
            set.sets[str] = true
            set.size++
        }
    }
    
    func (set *set) Remove(str string) error {
        v := set.sets[str]
        if v {
            set.sets[str] = false
            set.size--
            return nil
        }
        return errors.New("failed to remove,value is no exists.")
    }
    
    func (set *set) GetSize() int {
        return set.size
    }
    
    func (set *set) Contains(str string) bool {
        return set.sets[str]
    }
    
    func (set *set) IsEmpty() bool {
        return set.size == 0
    }
    

    分别用映射和集合来解决leetcode的804题目


    // 用映射解决方法
    func uniqueMorseRepresentations(words []string) int {
        m1 := map[int]string{}
        strs := []string{".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-",                       ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}
        for i, v := range strs {
            m1[97+i] = v
        }
    
        count := 0
        m2 := map[string]bool{}
        words = []string{"gin", "zen", "gig", "msg"}
        for _, str := range words {
            buf := ""
            for _, key := range str {
                v1, ok1 := m1[int(key)]
                if !ok1 {
                    buf=""
                    break
                }
                buf = buf + v1
            }
            if buf == "" {
                continue
            }
            v2 := m2[buf]
            if !v2 {
                m2[buf] = true
                count++
            }
        }
        return count
    }
    
    // 用集合解决方法
    func main() {
        m := map[string]string{}
        strs := []string{".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}
        for i, v := range strs {
            m[string(97+i)] = v
        }
        fmt.Println(m)
    
        s := set1.NewSet()
        words := []string{"gin", "zen", "gig", "msg"}
        for _, str := range words {
            buf := ""
            for _, v := range str {
                k, ok := m[string(v)]
                if !ok {
                    buf = ""
                    break
                }
                buf = buf + k
            }
            if buf == "" {
                continue
            }
            s.Add(buf)
        }
        fmt.Println(s.GetSize())
    }
    

    用这种方法实现的映射和集合的增删改查操作,时间复杂度都为O(1),但因为是无序的,在要求顺序输出,求最大值最小值这种操作都要去遍历整个集合,速度就较慢
    待续

    有bug欢迎指出,转载请注明出处。

    相关文章

      网友评论

        本文标题:(9)Go实现映射和集合

        本文链接:https://www.haomeiwen.com/subject/tsglgqtx.html