请记着 map 这个数据结构

一、背景

很多问题，都可以使用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-