请记着 map 这个数据结构

作者: | 更新日期:

很多问题,都可以使用map解决,如果不能,那只能使用树了。

本文首发于公众号:天空的代码世界,微信号:tiankonguse
原文地址:https://mp.weixin.qq.com/s/vS0JVIR1pnpgpFV-V_M42w

一、背景

很多问题,都可以使用map解决,如果不能,那只能使用树了。
由于 map 已经可以解决大多数问题了,所以请记住 map 这个数据结构。
善于使用这个数据结构,可以帮我们节省很多代码量。

PS:最近几天事情比较多,一直在思考工作上自己做的项目该如何优化,文章就被落下了。
不过,现在工作上的事情已经思考的差不多了,后面文章应该正常写吧。

二、集合 set

一种特殊的 map 叫做 set,即所谓的集合。

对于集合,只需要关注一个数据是否存在,而不需要其对应的其他信息,如计数或者关联的值。

通过集合这个数据结构,你可以解决重复数据相关的问题。

比如判断一个数组是否有重复的元素。
比如求两个数组的交集(去重)。
比如路径搜索时,一个点是否搜索过,也可以使用集合来判断。

三、映射 map

对于集合 set ,只储存了索引信息,有时候还需要对于的关联数据。
这个就需要映射 map 这个数据接口了。

这个关联数据根据不同的场景含义不一样。

比如求两个数组的交集(不去重),此时就需要map来计数了。
而对于数组中是否存在两个数之和等于指定数,也是使用map来查找。

四、哈希 hash

其实 hash 和 map 是等价的,但是理论上,hash 的速度更快,传说中时间复杂度是O(1)

所以有很多面试题,就需要留意了。

比如问:怎么在常数复杂度内完成插入元素、删除元素、判断元素是否存在三种操作?
一般我们一想,使用 map 至少也是 log(n)级别的,没法更快了。
而面试期望你回答的是使用hash

五、寻找重复的子树

题意:给一个二叉树,返回所有重复子树去重后的根节点。
重复定义:二叉树有相同的结构,且值相同。
去重定义:重复的子树,只输出其中任意一个。

这道题其实需要我们将一个子树当做集合或者 map 的key值了。

map的key值需要时可以比较大小的,如何做的?
答案是序列化,将树序列化为一种唯一的个数。
这样就可以使用序列化后的字符串来代表这个树了。

六、前K个高频元素

题意:给一个整数数组,求出现频率前 K 高的元素。
要求:要求复杂度小于O(n log(n))

思路:看到不合理的时间复杂度,那只能使用hash来解决了。
通过hash对所有整数进行计数O(n),然后再使用桶排序的方法按统计的数字排序O(n)
最后,逆向遍历桶,得到答案O(k)

七、最后

哈希(hash)、集合(set)、映射(map)三个数据结构其实很类似。
虽然传说中,哈希的各种操作复杂度都是O(1)的,但是实际场景中,大家都是使用map的居多。
哈希一般出现在面试题里,而map则更实用了,所以请记住常使用map这个数据结构。

-EOF-

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面打开下面的地址进行留言。如果下面没有地址,可以关注公众号留言。
原文地址:https://mp.weixin.qq.com/s/vS0JVIR1pnpgpFV-V_M42w

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越