第 4 章 查找表相关问题（18题）
[toc]
查找，是使用计算机处理问题时的一个最基本的任务，因此也是面试中非常常见的一类问题。很多算法问题的本质，就是要能够高效查找。学会使用系统库中的 Map 和 Set ，就已经成功了一半。
4-1 查找问题简介（1题）
例题1：LeetCode 第 349 题
题目要求：给定两个数组，写一个函数来计算它们的交集。例子：给定 num1= [1, 2, 2, 1], nums2 = [2, 2], 返回 [2]。提示：每个在结果中的元素必定是唯一的。我们可以不考虑输出结果的顺序。
题目难度：简单。
中文网址：https://leetcode-cn.com/problems/intersection-of-two-arrays/description/
英文网址：
求解思路：
思路1（未实现）：
思路关键：根据题意，我们很自然想到，逐个将数组 2 中的元素放到数组 1 中看看有没有，我们可以遍历查找，而二分查找是一个更好的选择。
思路的具体描述：因为使用二分查找算法要求数据是排好序的，因此首先对数组 1 排序，然后将数组 2 中的每个的元素依次到数组 1 中进行二分查找，如果查找到，就添加了结果集中。根据题目要求：“每个在结果中的元素必定是唯一的”，因此应该使用 Set 保存结果。
思路2（未实现）：
思路关键：不妨两个数组都排序：
数组1：1,2,3,4,5
数组2：1,1,1,2,3
规则如下：依次把数组 2 中的元素拿出来，跟数组 1 最开头的那个元素进行比较，如果不相同，直接丢弃，如果相同，把这个数加入到结果集中，用 Set 保存，并且数组 1 中开头的这个元素也要拿掉。我这里说的拿掉的意思是，遍历的时候，两个数组的索引都 +1。
思路3（推荐）：
思路关键：其实是我们更容易想到的算法，Set 不仅可以将结果去重，还可以帮我们进行查找。
思路的具体描述：首先将数组 1 全部放入 Set 中（因为题目要求每个在结果中的元素必定是唯一的，才可以这么做，例如 LeetCode 第 350 题就不能这么做了）。然后逐个将数组 2 中的元素检查在数组 1 中是否存在，使用 Set 的 contains 方法，如果存在就添加到最后的结果集中。
我的解答：https://gist.github.com/liweiwei1419/54f91cf8cce3d63c6c2e9bd0a18aee58
参考资料：
思考总结：
1、Set 是我们常用的数据结构，我们应该熟悉关于 Set 的常见的操作，以及关于 Set 的实现类的底层实现原理，例如 Java 语言中的 TreeSet 是红黑树实现（高级的平衡二分搜索树），HashSet 是散列表实现，熟悉理解了这些数据结构可以帮助我们高效解决问题。
4-2 map 的使用 Intersection of Two Arrays II（1题）
（完成）例题1：LeetCode 第 LeetCode 第 350 题。
题目要求：给定两个数组，写一个方法来计算它们的交集。例如：给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2]。注意：输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。我们可以不考虑输出结果的顺序。
跟进：
（1）如果给定的数组已经排好序呢？你将如何优化你的算法？
（2）如果 nums1 的大小比 nums2 小很多，哪种方法更优？
（3）如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？
题目难度：简单。
中文网址：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/description/
英文网址：
求解思路：
思路1：对两个数组进行排序，遇到一样的元素，就添加到最后的结果集，应该使用 List 来保存。
可以使用题目给出的例子作为测试用例。
思路2：使用 HashMap 就可以实现计算重复次数。
我的解答：https://gist.github.com/liweiwei1419/74ee4bc1d1443425ff6cc17df271a700
元素的出现的次数，就是我们须要关注的问题。这里提供一种 STL 为我们提供的容器的特性。
首先说明，上面的解法是正确的，但是我们要特别声明一下。在 C++ 中 map 是有默认值的：
如果我们想真正删除 C++ 中的 map，我们应该调用 map 的 erase 方法。
C++ 中的映射是有默认值的，并且在我们第 1 次访问 map 中的数据的时候，如果这个数据不存在，C++ 会帮我们插入到 map 中。这是 C++ 语言的特殊性。
下面我们摒弃 C++ 这种语言中关于 map 的特殊性，来做一种解法：
（1）第4-1节的问题
（2）第4-2节的问题
扩展：
数组的有序和查找问题通常是非常密切的，想到二分查找的思想。下一小节的时间性能如何？
4-3 Set 和 Map 不同底层实现的区别（5题）
二分搜索树可以做什么？
下面的改动虽然我们的改动非常小，但是在底层，我们使用了完全不同的数据结构，这样对时间复杂度有了很好的改进。
（完成）练习1：LeetCode 第 242 题 Valid Anagram
要求：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。
示例 1：输入: s = “anagram”, t = “nagaram”，输出: true。
示例 2：输入: s = “rat”, t = “car”，输出: false。
说明：你可以假设字符串只包含小写字母。
进阶：如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
题目难度：简单。
中文网址：https://leetcode-cn.com/problems/valid-anagram/description/
英文网址：
求解关键：字母异位词的意思就是，字母还是这些字母，它们出现的次数也不变，唯一变化的是出现的次序。
思路1：
思路2：使用两个字符数组，代表 26 个字母，每个数位存储每个字母出现的次数。
看看用一个字符数组是不是也可以完成。
思路3：和思路 2 是一样的，只不过是使用 HashMap 完成包含各个字母数量的统计。
我的解答：https://gist.github.com/liweiwei1419/38506cfb10a64dadce4a50290ccfe915
思路4：Python 的写法，看一看就可以了。
思路5：用 hash 的方法，不是很理解。
（未完成）练习2：LeetCode 第 202 题：Happy Number
题目要求：Happy Number。编写一个算法来判断一个数是不是“快乐数”。一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
题目难度：简单。
中文网址：https://leetcode-cn.com/problems/valid-anagram/description/
英文网址：
求解思路：将一个数到“它每个数位上的数的平方和”视为一个变换，则这个变换可以一直进行下去，直到变化的结果是 1 ，那么这个数就是“快乐数”。此时要注意了，如果在这个连续变换的过程中，中途变换的数字出现重复，则这个重复会循环出现，因此这个数就不是“快乐数”。那么检测这个变换中途的数字是否重复就可以使用 Set。
思考总结：很常规的一个问题，要多练习，特别要知道怎么样一步一步得到一个整数的每个数位上的数值。
（再做一遍）练习3：LeetCode 第 290 题 Word Pattern
题目要求：单词模式。给定一种 pattern(模式) 和一个字符串 str ，判断 str 是否遵循这种模式。这里的“遵循”指完全匹配，例如在pattern里的每个字母和字符串 str 中的每个非空单词存在双向单映射关系。例如：
pattern = “abba”, str = “dog cat cat dog”, 返回true.
pattern = “abba”, str = “dog cat cat fish”, 返回false.
pattern = “aaaa”, str = “dog cat cat dog” , 返回false.
pattern = “abba”, str = “dog dog dog dog” , 返回false.
说明：你可以假设 pattern str
题目难度：简单。
中文网址：https://leetcode-cn.com/problems/word-pattern/description/
英文网址：
求解关键：题目要求的“双向单映射”即要求不同的字母不能映射到相同的单词，例如最后一个例子，就不符合要求。即已经出现过的单词，就不能再添加到字典中了，因此我们还需要一个集合来判断添加到字典中的单词是否重复。
练习4：LeetCode 第 205 题 Isomorphic Strings
题目要求：同构字符串。给定两个字符串 s 和 t，判断它们是否是同构的。如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
题目难度：简单。
中文网址：https://leetcode-cn.com/problems/isomorphic-strings/description/
英文网址：
求解关键：
我的解答：https://gist.github.com/liweiwei1419/83bdc86fbc76f77c8db32b05711e57a8
（没有做完）练习5：LeetCode 第 451 题 Sort Characters By Frequency
题目要求：根据字符出现频率排序。给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
题目难度：中等。
中文网址：https://leetcode-cn.com/problems/sort-characters-by-frequency/description/
英文网址：
求解思路：这道题其实我们很容易能够想到做一次计数，即 counter 操作。但是在最后输出的时候，要按照出现的频率降序排列，这也难不倒我们，Java 中的 TreeSet 就是这样的数据结构，抽象地说，利用二分搜索树的顺序性，可以帮助我们完成对放入“集合”（这里是抽象的集合，不是针对这道问题的集合）中的元素的排序工作。
3 种排序思路：
（1）使用字符串排序，指定排序规则；
（2）使用 TreeSet（也要指定排序规则）；
（3）使用优先队列（最大堆，同样要指定排序规则）。
使用排序，给出排序规则。或者优先队列。
