数学（Math）
数论（Number Theory）
计算几何（Computation Geometry）
概率统计（Probability Statistics）
随机抽样
拓扑网络（Topology Network）
线性代数（Linear Algebra）
随机（Random）<br>
洗牌算法（Shuffle）
Fisher-Yates 算法
算法思想
分治（Divide and Conquer）
问题特征
应用场景
动态规划（Dynamic Programming）
模型特征
多阶段决策最优解模型
最优子结构
无后效性
重复子问题
常见类型
前缀和
区间动态规划
背包问题
状态压缩
计数问题
矩阵快速幂
数位动态规划
应用场景
枚举（Enumerating）
复杂度分析
大 O 复杂度表示法
分析方法
1. 只关注循环执行次数最多的一段代码
2. 加法法则：总复杂度等于量级最大的代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
常见的复杂度量级
O(1)：不存在循环语句、递归语句
O(logn)：二分查找
O(n)：一层循环
O(nlogn)：高级排序
O(m+n)、O(m*n)：两个数据规模
O(n^2)：排序
O(2^n)：排列
...
最好、最坏情况时间复杂度
平均情况时间复杂度
均摊时间复杂度
查找（Search）
二分查找（Binary Search）
二叉搜索树（Binary Search Tree）
B 树（B Tree）
哈希表（Hash Table）
海量数据
判断元素是否出现在集合中
使用布隆过滤器判断某个元素已存在于集合
找出出现次数最多的元素<br>
1. 根据数据特征设计哈希函数，要将数据集均等划分。<br>2. 使用哈希函数把数据集划分到多个小文件：<br> 相同元素存在于同一文件、单个文件数据量 <= 数据集大小。<br>3. 对每个小文件使用哈希表统计元素出现的个数。<br> 根据每个小文件中的元素出现频度、求出现次数最多的元素。<br>
找出出现次数最多的 N 个元素
1. 哈希函数把数据分流到多台机器上、用哈希函数拆分到多个小文件中；<br>2. 对每个小文件，使用哈希表统计元素出现频率；<br>3. 遍历哈希表，使用容量为 N 的小根堆收集 top N 元素；<br>4. 对每个文件小根堆（top N）进行外部排序或使用小根堆处理，得到最终 top N。
找出指定范围内未出现的元素<br>
1. 创建长度为数据集大小的位图，要求元素是非负整数，否则要做映射；<br>2. 遍历数据集，元素值对应位图的下标，修改该位置的值为 1；<br>3. 遍历位图，如某个位置上标记为 0，表示该元素在数据集中未出现。
找出指定范围内任意一个未出现的元素
1. 遍历数据集，根据元素的值，在区间计数数组上统计区间上元素个数；<br>2. 遍历区间计数数组，找到值小于 n/k 的区间编号 i，定为目标区间；<br>3. 遍历数据集，关注落在目标区间内的元素（num/(n/k) == i），位图位置 bitmap[num-(n/k)*i] 设为 1；<br>4. 遍历位图找到未被设为 1 的位置 j，则 j+(n/k)*i 即为第一个未出现的元素。
找出重复的元素<br>
使用哈希函数将元素分配到多台机器上，每台机器分别统计重复的值；<br>或将大文件拆分成多个小文件，每个小文件再用哈希表遍历找到重复的值。
求中位数
参考“找出指定范围内任意一个未出现的元素”的区间计数法：<br>1. 遍历数据集，根据元素的值，在区间计数数组上统计区间上元素个数。<br>2. 遍历计数数组，累计每个区间的计数，找出累计元素不过半与过半之间的区间编号<br>（比如 40 个数，前 0~k-1 区间上有 18 个，加上第 k 区间后超过 20 个，可知第 20 个数在第 k 区间第 2 个）。<br>3. 申请区间长度的数组，再次遍历数据集，关注出现在该区间的元素、做词频统计（找到该区间上的第 2 个元素）。
找出出现 2 次的元素<br>
比如元素值域是 [0, n]，则申请长度为 2n 的位图，用两个位置表示一个值出现的频率。<br>1. 遍历数据集，初次遇到 num 则把 bitmap[num*2+1] 和 bitmap[num*2] 设置为 01，<br> 第二次则设置为 10，第三次则设置为 11，还遇到则不再设置。<br>2. 遍历位图，如果发现 bitmap[num*2+1] 和 bitmap[num*2] 设置为 10，则该位置表示的则为出现 2 次的元素。
一致性哈希（Consistent Hashing）
算法实现
数据倾斜
