映射: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欢迎指出,转载请注明出处。
网友评论