数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
ListNode* vectorToListNode(vector<int> nums) {
if (nums.size() == 0) {
return nullptr;
}
ListNode* root = new ListNode(nums[0]);
ListNode* tmp = root;
for (int i = 1; i < nums.size(); i++) {
tmp->next = new ListNode(nums[i]);
tmp = tmp->next;
}
return root;
}
链表与数组恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。
对首尾结点的插入和删除的情况。
LRU缓存的实现：双链表+哈希表
class Solution {
public:
int getLength(ListNode* head) {
int length = 0;
while (head) {
++length;
head = head->next;
}
return length;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
int length = getLength(head);
ListNode* cur = dummy;
for (int i = 1; i < length - n + 1; ++i) {
cur = cur->next;
}
cur->next = cur->next->next;
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
// 迭代法
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* preHead = new ListNode(-1);
ListNode* prev = preHead;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
prev->next = l1;
l1 = l1->next;
} else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
prev->next = l1 == nullptr ? l2 : l1;
return preHead->next;
}
};
// 递归法
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) {
return l2;
} else if (l2 == nullptr) {
return l1;
} else if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};
// 是否有环
class Solution {
public:
bool hasCycle(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return false;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (fast == nullptr || fast->next == nullptr) {
return false;
}
slow = slow->next;
fast = fast->next->next;
}
return true;
}
};
// 返回交点的结点
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast != nullptr) {
slow = slow->next;
if (fast->next == nullptr) {
return nullptr;
}
fast = fast->next->next;
if (fast == slow) {
ListNode *ptr = head;
while (ptr != slow) {
ptr = ptr->next;
slow = slow->next;
}
return ptr;
}
}
return nullptr;
}
};
// 迭代法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};
// 递归法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};
后进者先出，先进者后出，这就是典型的“栈”结构。
先进者先出，这就是典型的“队列”。
参考链接
设计散列函数一般应遵循以下原则：
1.直接定址法
2.除留余数法
最常用的构造方法。对于散列表长为 m 的散列函数公式为 F ( key ) = key mod p ( p < m) , mod 是取模（求余数）。
3. 数字分析法
4.平方取中法
5. 折叠法
当哈希表关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，这样的现象称为哈希冲突。
1.开放地址法
基本思想：当发生地址冲突的时候，计算出另一个hash地址，直到找到不冲突的哈希地址。
有一个通用的再散列函数形式，Hi=（H（key）+di）% m i=1，2，…，n
其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：
(1).线性探测再散列
dii=1，2，3，…，m-1
这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
(2).二次探测再散列
di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )
这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
(3).伪随机探测再散列
di=伪随机数序列。
2.链地址法
将hash冲突的记录存储在统一链表中。
3.再哈希法
这种方法是同时构造多个不同的哈希函数：
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间，同时需要准备许多哈希函数。
4.建立公共溢出区
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，溢出表储存产生冲突的关键字。
总结
与开放地址法相比，拉链法有如下几个优点：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
STL中的哈希桶长度常数
哈希表的桶个数使用质数，可以最大程度减少冲突概率，使哈希后的数据分布的更加均匀。如果使用合数，可能会造成很多数据分布会集中在某些点上，从而影响哈希表效率。
假设索引有 h 级，最高级的索引有 2 个结点。通过上面的公式，我们可以得到 n/(2h)=2，从而求得 h=log2n-1。如果包含原始链表这一层，整个跳表的高度就是 log2n。我们在跳表中查询某个数据的时候，如果每一层都要遍历 m 个结点，那在跳表中查询一个数据的时间复杂度就是 O(m*logn)。
在跳表中查询任意数据的时间复杂度就是 O(logn)。
插入和删除操作的时间复杂度也是O(logn)。
当我们不停地往跳表中插入数据时，如果我们不更新索引，就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。
红黑树、AVL 树这样平衡二叉树，你就知道它们是通过左右旋的方式保持左右子树的大小平衡（如果不了解也没关系，我们后面会讲），而跳表是通过随机函数来维护前面提到的“平衡性”。
Redis 中的有序集合是通过跳表来实现的，严格点讲，其实还用到了散列表。不过散列表我们后面才会讲到，所以我们现在暂且忽略这部分。如果你去查看 Redis 的开发手册，就会发现，Redis 中的有序集合支持的核心操作主要有下面这几个：
其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。
对于按照区间查找数据这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做非常高效。
当然，Redis 之所以用跳表来实现有序集合，还有其他原因，比如，跳表更容易代码实现。虽然跳表的实现也不简单，但比起红黑树来说还是好懂、好写多了，而简单就意味着可读性好，不容易出错。还有，跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
不过，跳表也不能完全替代红黑树。因为红黑树比跳表的出现要早一些，很多编程语言中的 Map 类型都是通过红黑树来实现的。我们做业务开发的时候，直接拿来用就可以了，不用费劲自己去实现一个红黑树，但是跳表并没有一个现成的实现，所以在开发中，如果你想使用跳表，必须要自己实现。
叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做满二叉树。
叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。
二叉树遍历的时间复杂度为O(n)
二叉树的储存方式：链式储存法和顺序储存法。
二叉树的结构
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
前序遍历
// 递归
class Solution {
public:
void preorder(TreeNode *root, vector<int> &res) {
if (root == nullptr) {
return;
}
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
vector<int> preorderTraversal(TreeNode *root) {
vector<int> res;
preorder(root, res);
return res;
}
};
// 迭代
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (root == nullptr) {
return res;
}
stack<TreeNode*> stk;
TreeNode* node = root;
while (!stk.empty() || node != nullptr) {
while (node != nullptr) {
res.emplace_back(node->val);
stk.emplace(node);
node = node->left;
}
node = stk.top();
stk.pop();
node = node->right;
}
return res;
}
};
中序遍历
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while (root != nullptr || !stk.empty()) {
while (root != nullptr) {
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
res.push_back(root->val);
root = root->right;
}
return res;
}
};
后序遍历
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
if (root == nullptr) {
return res;
}
stack<TreeNode *> stk;
TreeNode *prev = nullptr;
while (root != nullptr || !stk.empty()) {
while (root != nullptr) {
stk.emplace(root);
root = root->left;
}
root = stk.top();
stk.pop();
if (root->right == nullptr || root->right == prev) {
res.emplace_back(root->val);
prev = root;
root = nullptr;
} else {
stk.emplace(root);
root = root->right;
}
}
return res;
}
};
二叉查找树，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
重要特性：中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。
在二叉查找树中，查找、插入、删除等很多操作的时间复杂度都跟树的高度成正比。两个极端情况的时间复杂度分别是 O(n) 和 O(logn)，分别对应二叉树退化成链表的情况和完全二叉树。
平衡二叉树定义：二叉树中任意一个节点的左右子树的高度相差不能大于 1。
平衡二叉查找树的高度接近 logn，所以插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)。
二叉查找树
在二叉查找树中，查找、插入、删除等很多操作的时间复杂度都跟树的高度成正比。两个极端情况的时间复杂度分别是 O(n) 和 O(logn)，分别对应二叉树退化成链表的情况和完全二叉树。
红黑树
红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。
平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。
平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。
红黑树是一种平衡二叉查找树。红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。
插入和删除都是基于左旋右旋和变色的。
红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况在数据较小，可以完全放到内存中时，红黑树的时间复杂度比B树低。
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
TreeNode* stringToTreeNode(vector<int> input) {
if (input.size() == 0) {
return nullptr;
}
int index = 0;
TreeNode* root = new TreeNode(input[index]);
queue<TreeNode*> nodeQueue;
nodeQueue.push(root);
while (true) {
TreeNode* node = nodeQueue.front();
nodeQueue.pop();
index++;
if (index == input.size()) {
break;
}
if (input[index] != 0) {
node->left = new TreeNode(input[index]);
nodeQueue.push(node->left);
}
index++;
if (index == input.size()) {
break;
}
if (input[index] != 0) {
node->right = new TreeNode(input[index]);
nodeQueue.push(node->right);
}
}
return root;
}
堆的定义： 堆是一个完全二叉树；堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做“小顶堆”。
堆的储存：完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。
建堆
第一种建堆思路的处理过程是从前往后处理数组数据，并且每个数据插入堆中时，都是从下往上堆化。而第二种实现思路，是从后往前处理数组，并且每个数据都是从上往下堆化。
private static void heapify(int[] a, int n, int i) {
while (true) {
int maxPos = i;
if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
if (maxPos == i) break;
swap(a, i, maxPos);
i = maxPos;
}
}
堆排序的应用： 优先级队列、求 Top K 问题和求中位数问题、合并有序小文件。
堆中比较重要的两个操作是插入一个数据和删除堆顶元素。这两个操作都要用到堆化。插入一个数据的时候，我们把新插入的数据放到数组的最后，然后从下往上堆化；删除堆顶数据的时候，我们把数组中的最后一个元素放到堆顶，然后从上往下堆化**。堆的插入和删除操作时间复杂度都是 O(logn)。**
第一点，堆排序数据访问的方式没有快速排序友好。对于快速排序来说，数据是顺序访问的。而对于堆排序来说，数据是跳着访问的，这样对CPU的缓存是不友好的，因为CPU对顺序访问的数据。
第二点，对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。
对于基于比较的排序算法来说，整个排序过程就是由两个基本的操作组成的，比较和交换（或移动）。快速排序数据交换的次数不会比逆序度多。但是堆排序的第一步是建堆，建堆的过程会打乱数据原有的相对先后顺序，导致原数据的有序度降低。比如，对于一组已经有序的数据来说，经过建堆之后，数据反而变得更无序了。因此，堆排序比快速排序的交换次数多。
散列表：插入删除查找都是O(1), 是最常用的，但其缺点是不能顺序遍历以及扩容缩容的性能损耗。适用于那些不需要顺序遍历，数据更新不那么频繁的。
跳表：插入删除查找都是O(logn), 并且能顺序遍历。缺点是空间复杂度O(n)。适用于不那么在意内存空间的，其顺序遍历和区间查找非常方便。
红黑树：插入删除查找都是O(logn), 中序遍历即是顺序遍历，稳定。缺点是难以实现，去查找不方便。其实跳表更佳，但红黑树已经用于很多地方了。
图的概念：无向图、有向图、带权图、顶点、边、度、入度、出度。
图的两种储存方式：连接矩阵和邻接表。
两种储存方式的比较： 邻接矩阵存储方法的缺点是比较浪费空间，但是优点是查询效率高，而且方便矩阵运算。邻接表存储方法中每个顶点都对应一个链表，存储与其相连接的其他顶点。尽管邻接表的存储方式比较节省存储空间，但链表不方便查找，所以查询效率没有邻接矩阵存储方式高。针对这个问题，邻接表还有改进升级版，即将链表换成更加高效的动态数据结构，比如平衡二叉查找树、跳表、散列表等。
dfs, bfs, 拓扑排序，关节点，单源最短路径,最短生成路径，Dijkstra。
BF和RK BM和KMP
BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，
算法思想：拿模式串与主串中是所有子串匹配，看是否有能匹配的子串。
复杂度分析
BF 算法的时间复杂度很高，是 O(n*m)，n、m 表示主串和模式串的长度。不过，在实际的软件开发中，因为这种算法实现简单，对于处理小规模的字符串匹配很好用。
为什么在实际开发中，BF算法是一个比较常用的字符串匹配算法？
RK 算法的全称叫 Rabin-Karp 算法，它其实就是刚刚讲的 BF 算法的升级版，引入了哈希算法，降低了时间复杂度。
RK 算法的思路是这样的：我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。理想情况下，RK 算法的时间复杂度是 O(n)，跟 BF 算法相比，效率提高了很多。不过这样的效率取决于哈希算法的设计方法，如果存在冲突的情况下，时间复杂度可能会退化。极端情况下，哈希算法大量冲突，时间复杂度就退化为 O(n*m)。
这就需要哈希算法设计的非常有技巧了。我们假设要匹配的字符串的字符集中只包含 K 个字符，我们可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。
整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。第一部分，我们前面也分析了，可以通过设计特殊的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是 O(n)。
模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1)，总共需要比较 n-m+1 个子串的哈希值，所以，这部分的时间复杂度也是 O(n)。所以，RK 算法整体的时间复杂度就是 O(n)。
哈希冲突
实际上，解决方法很简单。当我们发现一个子串的哈希值跟模式串的哈希值相等的时候，我们只需要再对比一下子串和模式串本身就好了。当然，如果子串的哈希值与模式串的哈希值不相等，那对应的子串和模式串肯定也是不匹配的，就不需要比对子串和模式串本身了。
所以，哈希算法的冲突概率要相对控制得低一些，如果存在大量冲突，就会导致 RK 算法的时间复杂度退化，效率下降。极端情况下，如果存在大量的冲突，每次都要再对比子串和模式串本身，那时间复杂度就会退化成 O(n*m)。但也不要太悲观，一般情况下，冲突不会很多，RK 算法的效率还是比 BF 算法高的。
原理分析
BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。
BM 算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。BM 算法构建的规则有两类，坏字符规则和好后缀规则。
坏字符规则
从模式串的末尾往前倒着匹配，当发现某个字符没法匹配的时候，我们把这个没有匹配的字符叫作坏字符（主串中的字符）。
当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。（注意，我这里说的下标，都是字符在模式串的下标）。
利用坏字符规则，BM 算法在最好情况下的时间复杂度非常低，是 O(n/m)。
好后缀规则
好后缀规则实际上跟坏字符规则的思路很类似。你看我下面这幅图。当模式串滑动到图中的位置的时候，模式串和主串有 2 个字符是匹配的，倒数第 3 个字符发生了不匹配的情况。
我们把已经匹配的 bc 叫作好后缀，记作{u}。我们拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u*}，那我们就将模式串滑动到子串{u*}与主串中{u}对齐的位置。
如果在模式串中找不到另一个等于{u}的子串，我们就直接将模式串，滑动到主串中{u}的后面，因为之前的任何一次往后滑动，都没有匹配主串中{u}的情况。
不过，当模式串中不存在等于{u}的子串时，我们直接将模式串滑动到主串{u}的后面。这样做是否有点太过头呢？我们来看下面这个例子。这里面 bc 是好后缀，尽管在模式串中没有另外一个相匹配的子串{u*}，但是如果我们将模式串移动到好后缀的后面，如图所示，那就会错过模式串和主串可以匹配的情况。
如果好后缀在模式串中不存在可匹配的子串，那在我们一步一步往后滑动模式串的过程中，只要主串中的{u}与模式串有重合，那肯定就无法完全匹配。但是当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。
所以，针对这种情况，我们不仅要看好后缀在模式串中，是否有另一个匹配的子串，我们还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。所谓某个字符串 s 的后缀子串，就是最后一个字符跟 s 对齐的子串，比如 abc 的后缀子串就包括 c, bc。所谓前缀子串，就是起始字符跟 s 对齐的子串，比如 abc 的前缀子串有 a，ab。我们从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是{v}，然后将模式串滑动到如图所示的位置。
算法性能分析
BM 算法的时间复杂度分析起来是非常复杂，BM 算法的比较次数上限是 3n~5n。
算法的基本原理
我们假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。
最长可匹配后缀子串和最长可匹配前缀子串
KMP 算法也可以提前构建一个数组，用来存储模式串中每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标。我们把这个数组定义为 next 数组，很多书中还给这个数组起了一个名字，叫失效函数（failure function）。
复杂度分析
空间复杂度很容易分析，KMP 算法只需要一个额外的 next 数组，数组的大小跟模式串相同。所以空间复杂度是 O(m)，m 表示模式串的长度。
KMP 算法包含两部分，第一部分是构建 next 数组，第二部分才是借助 next 数组匹配。所以，关于时间复杂度，我们要分别从这两部分来分析。
next 数组计算的时间复杂度是 O(m)。next数组匹配这部分的时间复杂度是 O(n)。KMP 算法的时间复杂度是 O(n+m)
class Solution {
public:
// a表示主串，n是主串的长度，b表示模式串，m模式串的长度
int kmp(vector<char>& a, int n, vector<char>& b, int m) {
vector<int> nexts = getNexts(b, m);
int j = 0;
for (int i = 0; i < n; i++) {
// 一直找到主串与模式串相等的字符
// 通过失效函数计算最大的滑动距离
while (j > 0 && a[i] != b[j]) {
j = nexts[j - 1] + 1;
}
if (a[i] == b[j]) {
++j;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
// 失效函数，b是模式串，m模式串的长度
// 主要思想：动态规划
vector<int> getNexts(vector<char>& b, int m) {
vector<int> nexts(m);
nexts[0] = -1;
// k是最长可匹配前缀子串的长度
int k = -1;
for (int i = 1; i < m; i++) {
// 找到最长可匹配前缀子串的长度
while (k != -1 && b[k + 1] != b[i]) {
k = nexts[k];
}
// 如果当前字符等于最长可匹配前缀子串的下一个字符
// 则k = k + 1;
if (b[k + 1] == b[i]) {
++k;
}
// 当前字符可匹配前缀子串的长度
nexts[i] = k;
}
return nexts;
}
};
稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
我通过一个例子来解释一下。比如我们有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。这组数据里有两个 3。经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
算法性能分析
平均时间复杂度
O
(
n
2
)
O(n^2)
O(n2)；最好情况
O
(
n
)
O(n)
O(n)；最坏情况
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度：
O
(
1
)
O(1)
O(1)；原地排序；稳定性排序
遍历数组，找到数据应该插入的位置将其插入即可。
首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
算法性能分析
平均时间复杂度
O
(
n
2
)
O(n^2)
O(n2)；最好情况
O
(
n
)
O(n)
O(n)；最坏情况
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度：
O
(
1
)
O(1)
O(1)；原地排序；稳定性排序
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
算法性能分析
平均时间复杂度
O
(
n
2
)
O(n^2)
O(n2)；最好情况
O
(
n
2
)
O(n^2)
O(n2)；最坏情况
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度：
O
(
1
)
O(1)
O(1)；原地排序；非稳定性排序
桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
算法性能分析
平均时间复杂度
O
(
n
+
k
)
O(n + k)
O(n+k)；最好情况
O
(
n
+
k
)
O(n + k)
O(n+k)；最坏情况
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度：
O
(
n
+
k
)
O(n + k)
O(n+k)；非原地排序；稳定性排序
计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
举例：
考生的满分是 900 分，最小是 0 分，这个数据的范围很小，所以我们可以分成 901 个桶，对应分数从 0 分到 900 分。根据考生的成绩，我们将这 50 万考生划分到这 901 个桶里。桶内的数据都是分数相同的考生，所以并不需要再进行排序。我们只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了 50 万考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是 O(n)。
算法性能分析
平均时间复杂度
O
(
n
+
k
)
O(n + k)
O(n+k)；最好情况
O
(
n
+
k
)
O(n + k)
O(n+k)；最坏情况
O
(
n
+
k
)
O(n + k)
O(n+k)
空间复杂度：
O
(
k
)
O(k)
O(k)；非原地排序；稳定性排序
归并排序的思想：如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。
算法性能分析
平均时间复杂度
O
(
n
log
n
)
O(n\log n)
O(nlogn)；最好情况
O
(
n
log
n
)
O(n\log n)
O(nlogn)；最坏情况
O
(
n
log
n
)
O(n\log n)
O(nlogn)
空间复杂度：
O
(
n
)
O(n)
O(n)；非原地排序；稳定性排序
伪代码
// 归并排序算法, A是数组，n表示数组大小
merge_sort(A, n) {
merge_sort_c(A, 0, n-1)
}
// 递归调用函数
merge_sort_c(A, p, r) {
// 递归终止条件
if p >= r then return
// 取p到r之间的中间位置q
q = (p+r) / 2
// 分治递归
merge_sort_c(A, p, q)
merge_sort_c(A, q+1, r)
// 将A[p...q]和A[q+1...r]合并为A[p...r]
merge(A[p...r], A[p...q], A[q+1...r])
}
代码实现
void mergeSort(vector<int>& nums, vector<int>& tmp, int l, int r) {
if (l >= r) {
return ;
}
int mid = (l + r) / 2;
mergeSort(nums, tmp, l, mid);
mergeSort(nums, tmp, mid + 1, r);
int i = l, j = mid + 1, pos = l;
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[pos++] = nums[i++];
}
else {
tmp[pos++] = nums[j++];
}
}
for (int k = i; k <= mid; ++k) {
tmp[pos++] = nums[k];
}
for (int k = j; k <= r; ++k) {
tmp[pos++] = nums[k];
}
copy(tmp.begin() + l, tmp.begin() + r + 1, nums.begin() + l);
}
快排的思想：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
算法性能分析
平均时间复杂度
O
(
n
log
n
)
O(n\log n)
O(nlogn)；最好情况
O
(
n
log
n
)
O(n\log n)
O(nlogn)；最坏情况
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度：
O
(
log
n
)
O(\log n)
O(logn)；原地排序；非稳定性排序
快排的递归及非递归实现
// 快速排序，A是数组，n表示数组的大小
quick_sort(A, n) {
quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r为下标
quick_sort_c(A, p, r) {
if p >= r then return
q = partition(A, p, r) // 获取分区点
quick_sort_c(A, p, q-1)
quick_sort_c(A, q+1, r)
}
代码实现
int partition(vector<int>& a, int l, int r) {
int x = a[r], i = l - 1;
for (int j = l; j < r; ++j) {
if (a[j] <= x) {
swap(a[++i], a[j]);
}
}
swap(a[i + 1], a[r]);
return i + 1;
}
void quicksort(vector<int>& a, int l, int r) {
if (l >= r) return;
int i = partition(a, l, r);
quicksort(a, l, i - 1);
quicksort(a, i + 1, r);
}
可以发现，归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。
这个过程有点类似上面讲的“删除堆顶元素”的操作，当堆顶元素移除之后，我们把下标为 n 的元素放到堆顶，然后再通过堆化的方法，将剩下的 n−1 个元素重新构建成堆。堆化完成之后，我们再取堆顶的元素，放到下标是 n−1 的位置，一直重复这个过程，直到最后堆中只剩下标为 1 的一个元素，排序工作就完成了。
我们可以把堆排序的过程大致分解成两个大的步骤，建堆和排序。
算法性能分析
平均时间复杂度
O
(
n
log
n
)
O(n\log n)
O(nlogn)；最好情况
O
(
n
log
n
)
O(n\log n)
O(nlogn)；最坏情况
O
(
n
log
n
)
O(n\log n)
O(nlogn)
空间复杂度：
O
(
1
)
O(1)
O(1)；原地排序；非稳定性排序
// 递归方式构建大根堆(len是arr的长度，index是第一个非叶子节点的下标)
void adjust(vector<int> &arr, int len, int index)
{
int left = 2*index + 1; // index的左子节点
int right = 2*index + 2;// index的右子节点
int maxIdx = index;
if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
if(right<len && arr[right] > arr[maxIdx]) maxIdx = right;
if(maxIdx != index)
{
swap(arr[maxIdx], arr[index]);
adjust(arr, len, maxIdx);
}
}
// 堆排序
void heapSort(vector<int> &arr, int size)
{
// 构建大根堆（从最后一个非叶子节点向上）
for(int i=size/2 - 1; i >= 0; i--)
{
adjust(arr, size, i);
}
// 调整大根堆
for(int i = size - 1; i >= 1; i--)
{
swap(arr[0], arr[i]); // 将当前最大的放置到数组末尾
adjust(arr, i, 0); // 将未完成排序的部分继续进行堆排序
}
}
考前再看《极客时间》
广度优先搜索（Breadth-First-Search），我们平常都简称 BFS。直观地讲，它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。
public void bfs(int s, int t) {
if (s == t) return;
boolean[] visited = new boolean[v];
visited[s]=true;
Queue<Integer> queue = new LinkedList<>();
queue.add(s);
int[] prev = new int[v];
for (int i = 0; i < v; ++i) {
prev[i] = -1;
}
while (queue.size() != 0) {
int w = queue.poll();
for (int i = 0; i < adj[w].size(); ++i) {
int q = adj[w].get(i);
if (!visited[q]) {
prev[q] = w;
if (q == t) {
print(prev, s, t);
return;
}
visited[q] = true;
queue.add(q);
}
}
}
}
private void print(int[] prev, int s, int t) { // 递归打印s->t的路径
if (prev[t] != -1 && t != s) {
print(prev, s, prev[t]);
}
System.out.print(t + " ");
}
复杂度分析
最坏情况下，终止顶点 t 离起始顶点 s 很远，需要遍历完整个图才能找到。这个时候，每个顶点都要进出一遍队列，每个边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O(V+E)，其中，V 表示顶点的个数，E 表示边的个数。当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O(E)。
广度优先搜索的空间消耗主要在几个辅助变量 visited 数组、queue 队列、prev 数组上。这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V)。
深度优先搜索（Depth-First-Search），简称 DFS。最直观的例子就是“走迷宫”。深度优先搜索用的是一种比较著名的算法思想，回溯思想。
boolean found = false; // 全局变量或者类成员变量
public void dfs(int s, int t) {
found = false;
boolean[] visited = new boolean[v];
int[] prev = new int[v];
for (int i = 0; i < v; ++i) {
prev[i] = -1;
}
recurDfs(s, t, visited, prev);
print(prev, s, t);
}
private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
if (found == true) return;
visited[w] = true;
if (w == t) {
found = true;
return;
}
for (int i = 0; i < adj[w].size(); ++i) {
int q = adj[w].get(i);
if (!visited[q]) {
prev[q] = w;
recurDfs(q, t, visited, prev);
}
}
}
复杂度分析
深度优先搜索算法的时间复杂度是 O(E)，E 表示边的个数。
深度优先搜索算法的消耗内存主要是 visited、prev 数组和递归调用栈。visited、prev 数组的大小跟顶点的个数 V 成正比，递归调用栈的最大深度不会超过顶点的个数，所以总的空间复杂度就是 O(V)。
回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。
算法思想
二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
时间复杂度分析
处理的元素个数为
n
n
n
第1次循环所要处理的元素是
n
n
n
第2次循环所要处理的元素是
1
2
n
\frac{1}{2}n
21n
⋯
\cdots
⋯
第
k
k
k次循环所要处理的元素是
1
2
k
n
\frac{1}{2^{k}}n
2k1n
循环停止的条件为
1
2
k
n
=
1
\frac{1}{2^{k}}n = 1
2k1n=1
因为
1
2
k
n
≥
1
\frac{1}{2^{k}}n \geq 1
2k1n≥1，取整后当为1时停止循环
解得上式
k
=
log
2
n
k = \log_{2}{n}
k=log2n
所以时间复杂度为
O
(
log
2
n
)
O(\log_{2}{n})
O(log2n)
递归和非递归代码实现
int bsearch(int a[], int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == value) {
return mid;
}
else if (a[mid] < value) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return -1;
}
int bsearchInternally(int a[], int low, int high, int value) {
if (low > high) return -1;
int mid = low + ((high - low) >> 1);
if (a[mid] == value) {
return mid;
}
else if (a[mid] < value) {
return bsearchInternally(a, mid + 1, high, value);
}
else {
return bsearchInternally(a, low, mid - 1, value);
}
}
二分查找的局限性
查找第一个值等于给定值的元素
// 第一个等于给定值的元素
int bsearch(vector<int>& a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
}
else if (a[mid] < value) {
low = mid + 1;
}
else {
if ((mid == 0) || (a[mid - 1] != value)) return mid;
else high = mid - 1;
}
}
return -1;
}
查找最后一个值等于给定的元素
// 最后一个等于给定值的元素
int bsearchlast(vector<int>& a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
}
else if (a[mid] < value) {
low = mid + 1;
}
else {
if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
else low = mid + 1;
}
}
return -1;
}
查找第一个大于等于给定值的元素
int bsearchgreat(vector<int>& a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
if ((mid == 0) || (a[mid - 1] < value)) return mid;
else high = mid - 1;
}
else {
low = mid + 1;
}
}
return -1;
}
查找最后一个小于等于给定值的元素
int bsearchlower(vector<int>& a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
}
else {
if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
else low = mid + 1;
}
}
return -1;
}
146. LRU 缓存机制.
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
方法一：哈希表 + 双向链表
LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。
这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：
对于 get 操作，首先判断 key 是否存在：
对于 put 操作，首先判断 key 是否存在：
上述各项操作中，访问哈希表的时间复杂度为 O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O(1) 时间内完成。
小贴士
在双向链表的实现中，使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。
struct DLinkedNode {
int key, value;
DLinkedNode* prev;
DLinkedNode* next;
DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
unordered_map<int, DLinkedNode*> cache;
DLinkedNode* head;
DLinkedNode* tail;
int size;
int capacity;
public:
LRUCache(int _capacity): capacity(_capacity), size(0) {
// 使用伪头部和伪尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (!cache.count(key)) {
return -1;
}
// 如果 key 存在，先通过哈希表定位，再移到头部
DLinkedNode* node = cache[key];
moveToHead(node);
return node->value;
}
void put(int key, int value) {
if (!cache.count(key)) {
// 如果 key 不存在，创建一个新的节点
DLinkedNode* node = new DLinkedNode(key, value);
// 添加进哈希表
cache[key] = node;
// 添加至双向链表的头部
addToHead(node);
++size;
if (size > capacity) {
// 如果超出容量，删除双向链表的尾部节点
DLinkedNode* removed = removeTail();
// 删除哈希表中对应的项
cache.erase(removed->key);
// 防止内存泄漏
delete removed;
--size;
}
}
else {
// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
DLinkedNode* node = cache[key];
node->value = value;
moveToHead(node);
}
}
void addToHead(DLinkedNode* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
void removeNode(DLinkedNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void moveToHead(DLinkedNode* node) {
removeNode(node);
addToHead(node);
}
DLinkedNode* removeTail() {
DLinkedNode* node = tail->prev;
removeNode(node);
return node;
}
};
算法思想：Dijkstra 算法有点儿类似 BFS 算法，利用贪心的思想，它每次找到跟起点最近的顶点，往外扩展。
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
const int inf = INT_MAX / 2;
vector<vector<pair<int, int>>> g(n);
for (auto& time : times) {
g[time[0] - 1].emplace_back(time[1] - 1, time[2]);
}
vector<int> dist(n, inf);
dist[k - 1] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
q.emplace(0, k - 1);
while (!q.empty()) {
auto [time, now] = q.top();
q.pop();
if (dist[now] < time) {
continue;
}
for (auto [next, nextTime] : g[now]) {
int cur = dist[now] + nextTime;
if (dist[now] + nextTime < dist[next]) {
dist[next] = cur;
q.emplace(cur, next);
}
}
}
int ans = *max_element(dist.begin(), dist.end());
return ans == inf ? -1 : ans;
}
算法流程
时间复杂度分析： 内部的for循环最多执行E次，时间复杂度为O(E)，E为图中所有边的个数。for循环内部的代码主要涉及优先队列的增删，时间复杂度是O(log V)，V为顶点的个数。总的时间复杂度为O(E log V)
我们今天讲的 A* 算法属于一种启发式搜索算法（Heuristically Search Algorithm）。
启发式搜索算法利用估价函数，避免“跑偏”，贪心地朝着最有可能到达终点的方向前进。
顶点与起点的路径长度g(i)，顶点到终点的路径长度估计值h(i)，通过两者之和f(i) = g(i) + h(i)。f(i)是估价函数。h(i)就是启发函数，通常有欧几里得距离和曼哈顿距离。欧几里得距离：两点之间的直线距离，开根号计算。曼哈顿距离：两点之间的横纵坐标的距离。
可将dijstra算法改造之后成为A*算法。
A*算法与dijstra算法的区别：
尽管 A 算法可以更加快速地找到从起点到终点的路线，但是它并不能像 Dijkstra 算法那样，找到最短路线。这是为什么呢？*
Dijkstra 算法是在终点出队列的时候才结束，A* 算法是一旦遍历到终点就结束。对于 Dijkstra 算法来说，当终点出队列的时候，终点的 dist 值是优先级队列中所有顶点的最小值，即便再运行下去，终点的 dist 值也不会再被更新了。对于 A* 算法来说，一旦遍历到终点，我们就结束 while 循环，这个时候，终点的 dist 值未必是最小值。
链表的每一个节点内部都存有两部分数据，一个是数据， 另一个则是地址。
数组+结构体实现。数组元素中存放结构体，结构体中一个表示数据，另一个表示其下一个节点在数组中的下标。
Bitmap简介
bitmap是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此可以大大节省存储空间。
应用
4亿个qq，1G内存，查找在不在其中
解析：
Bit-map的基本思想就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。（PS：划重点 节省存储空间）
假设有这样一个需求：在20亿个随机整数中找出某个数m是否存在其中，并假设32位操作系统，4G内存
在Java中，int占4字节，1字节=8位（1 byte = 8 bit）
如果每个数字用int存储，那就是20亿个int，因而占用的空间约为 (2000000000*4/1024/1024/1024)≈7.45G
如果按位存储就不一样了，20亿个数就是20亿位，占用空间约为 (2000000000/8/1024/1024/1024)≈0.233G
首先找该数所在的字节的位，对于添加按位或1，删除按位与0（1取反），查找按位与1。
直接全部排序（只适用于内存够的情况）
当数据量较小的情况下，内存中可以容纳所有数据。则最简单也是最容易想到的方法是将数据全部排序，然后取排序后的数据中的前K个。
最大堆法
这是一种局部淘汰法。先读取前K个数，建立一个最小堆。然后将剩余的所有数字依次与最小堆的堆顶进行比较，如果小于或等于堆顶数据，则继续比较下一个；否则，删除堆顶元素，并将新数据插入堆中，重新调整最小堆。当遍历完全部数据后，最小堆中的数据即为最大的K个数。
分治法
将全部数据分成N份，前提是每份的数据都可以读到内存中进行处理，找到每份数据中最大的K个数。此时剩下NK个数据，如果内存不能容纳NK个数据，则再继续分治处理，分成M份，找出每份数据中最大的K个数，如果M*K个数仍然不能读到内存中，则继续分治处理。直到剩余的数可以读入内存中，那么可以对这些数使用快速排序的变形或者归并排序进行处理。
Hash法
如果这些数据中有很多重复的数据，可以先通过hash法，把重复的数去掉。这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间。处理后的数据如果能够读入内存，则可以直接排序；否则可以使用分治法或者最小堆法来处理数据。