两类查找问题

  • 查找有无

元素 a 是否存在？set；集合

  • 查找对应关系（键值对应）

元素 a 出现了几次？map；字典或映射

set和map

C++语言中，

set 和 map 的底层实现为平衡二叉树

unordered_set 和 unordered_map 的底层实现为哈希表

通常语言的标准库中都内置 set 和 map

容器类

屏蔽实现细节

了解语言中标准库里常见容器类的使用

常见操作

insert

find

erase

change(map)

set 和 map 可以有不同的底层实现

底层实现

普通数组实现 顺序数组实现 二叉查找树（平衡） 哈希表
插入 O(1) O(n) O(logn) O(1)
查找 O(n) O(logn) O(logn) O(1)
删除 O(n) O(n) O(logn) O(1)

数据的顺序性

  • 数据集中的最大值和最小值

  • 某个元素的前驱和后继

  • 某个元素的 floor 和 ceil

  • 某个元素的排位 rank

  • 选择某个排位的元素 select

面试实战

  • Intersection of Two Arrays(#349)

  • Intersection of Two Arrays(#350)

  • Two Sum(#1)

  • 4Sum-II(#454)

  • Number of Boomeranges(#447)

  • Contains Duplicate II(#219 )

  • Contains Duplicate III(#220 )

程序

见代码。