| 问题 | 数据结构 | 算法 | 描述 | 效率 | 举例 | |
| 统计 | 最大|最小 | 数组 | 逐个比较 | O(n) | ||
| 最大&最小 | 数组 |
每两个做输入，先在输入中比大小； 较小者去比较最小记录，较大者去比较最大记录； |
O(3n/2) | |||
| 第K大 | 快排选择 | O(n) | ||||
| 前K大 | 堆（优先队列） |
建堆； 取K次最大 |
O(N) + k*logN | |||
| 排序 | 要求完全有序 | 快排 | O(N*logN) | |||
|
要求取最大/最小； 可增加、删除元素； |
堆（优先队列） |
|
取最大/最小 O(logN) 增加/删除 O(logN) |
操作系统按任务优先级调度作业 | ||
| 查找 | 最新一个/最旧一个 | 栈/队列 | O(1) | |||
| 某个 | 哈希表 |
冲突解决方法： 线性探测法，开链法（申请、释放内存，效率低）； 当填充因子较大，需要再哈希 |
O(1) | |||
|
某个； 找前驱后继； 最大最小； 没有增加&删除 |
二叉查找树 | 如果有增加、删除操作，可能导致退化成链表 | 都logN | |||
|
某个； 找前驱后继； 最大最小； 可增加&删除 |
红黑树 | 都logN | ||||
| 找最*的N个元素 | 分治法 |
把集合分成若干（通常是2）份； 递归往下，找到每份中符合条件元素，比较出最符合条件的那个； |
最近点； 凸包问题（最外层的点）； |
|||
| 求排列、子集 | 减治法 | f(n) = f(n-1) + ... | ||||
| 字符串匹配 | 时空权衡法 | 模式串是不会变的，所以，可以提前总结模式串的规律，并保存 |
原文：http://www.cnblogs.com/johnchow/p/5424239.html