一. 基础算法
（一） 常见查找算法
查找算法是一种在数据集中寻找特定数据项的方法。通常，数据集是在计算机程序中存储的，例如数组、链表或散列表。在编写程序时，查找算法是非常重要的，它有助于快速找到所需的数据。
（1） 线性查找
线性查找也称为顺序查找，是一种最简单的查找算法。在这种算法中，我们从数据集的开头开始，逐个比较每个数据项，以寻找要查找的数据。如果我们找到了目标数据，查找过程就结束了。如果我们到达数据集的末尾，仍然找不到目标数据，则可以认为它不存在于数据集中。
线性查找的时间复杂度是O(n)，其中n是数据集的大小。因此，它在大型数据集中可能会很慢。然而，在小型数据集中，它仍然是一种非常有用的算法。
（2） 二分查找
二分查找也称为折半查找，是一种更快速的查找算法。但前提是，数据集必须已经排序。在二分查找中，我们取数据集的中间值，然后将目标与中间值进行比较。如果目标小于中间值，则在左侧子集中继续查找；如果目标大于中间值，则在右侧子集中继续查找。每次比较都会缩小要搜索的数据集的大小。
二分查找的时间复杂度是 O(log n)，其中n是数据集的大小。这种算法在大型数据集中非常有效，但在小型数据集中可能并不是最快的选择。
（3）哈希表查找
哈希表查找也称为散列表查找，是另一种常见的查找算法。它利用哈希函数将数据项映射到散列表中的位置。在查找过程中，我们只需通过哈希函数计算目标数据的位置，然后检查该位置是否包含目标数据。
哈希表查找的时间复杂度是 O(1)。这使得它成为大型数据集中最快的查找算法之一。但是，哈希表查找的效率取决于哈希函数的质量。如果两个数据项映射到相同的位置，就会发生哈希冲突，这可能会导致性能下降。
（4）小结
在编写程序时，我们需要选择适合数据集大小和其他要求的最佳查找算法。例如，如果数据集很小，则线性查找可能是最快的选择；如果数据集已经排序，则二分查找是非常有用的。然而，在大型数据集中，哈希表查找通常是最好的选择。了解不同类型的查找算法及其特点可以帮助我们在编写程序时做出明智的选择。
二. 高效查找相关数据结构
不管是之前学过的数组、链表、队列、还是栈，这些线性结构中，如果想在其中查找一个元素，效率是比较慢的，只有 O(N)，因此如果你的需求是实现数据的快速查找，那么就需要新的数据结构支持。
还记得最先介绍的那个二分查找算法吗？它的查找效率能够达到 O(\log{N})，是不是还不错？不过呢，它需要对数组事先排好序，而排序的成本是比较高的。那么有没有一个折中的办法呢？有，那就是接下来要给大家介绍的二叉搜索树，它插入元素后，自然就是排好序的，接下来的查询也自然而然可以应用二分查找算法进行高效搜索。
1. 二叉搜索树
在计算机科学的发展中，二叉搜索树成为了一种非常基础的数据结构，被广泛应用在各种领域，包括搜索、排序、数据库索引等。随着计算机算力的提升和对数据结构的深入研究，二叉搜索树也不断被优化和扩展，例如AVL树、红黑树等。
1.1 特性
二叉搜索树（也称二叉排序树）是符合下面特征的二叉树：
- 树节点增加 key 属性，用来比较谁大谁小，key 不可以重复
- 对于任意一个树节点，它的 key 比左子树的 key 都大，这里指的是 “都” ，每个父节点都是后辈取值的分水岭。，同时也比右子树的 key 都小，（左小右大）例如下图所示
轻易看出要查找 7 （从根开始）自然就可应用二分查找算法，只需三次比较
- 与 4 比，较之大，向右找
- 与 6 比，较之大，继续向右找
- 与 7 比，找到
查找的时间复杂度与树高相关，插入、删除也是如此。
- 如果这棵树长得还不赖（左右平衡）上图，那么时间复杂度均是
O(\log{N}) - 当然，这棵树如果长得丑（左右高度相差过大）下图，那么这时是最糟的情况，时间复杂度是
O(N)
注：
- 二叉搜索树 - 英文 binary search tree，简称
BST- 二叉排序树 - 英文 binary ordered tree 或 binary sorted tree
1.2 定义节点
static class BSTNode {
int key; // 若希望任意类型作为 key, 则后续可以将其设计为 Comparable 接口
Object value;
BSTNode left;
BSTNode right;
public BSTNode(int key) {
this.key = key;
this.value = key; // ....
}
public BSTNode(int key, Object value) {
this.key = key;
this.value = value;
}
public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
1.3 查找get
力扣相似题目：700. 二叉搜索树中的搜索
递归实现：
public Object get(int key) {
return doGet(root, key);
}
private Object doGet(BSTNode node, int key) {
if (node == null) {
return null; // 没找到
}
if (key < node.key) {
return doGet(node.left, key); // 向左找
} else if (node.key < key) {
return doGet(node.right, key); // 向右找
} else {
return node.value; // 找到了
}
}
非递归实现：
/**
* <h3>查找关键字对应的值</h3>
* 比父节点小 往左，否则往右
* @param key 关键字
* @return 关键字对应的值
*/
public Object get(int key) {
BSTNode node = root;
while (node != null) {
if (key < node.key) {
node = node.left;
} else if (node.key < key) {
node = node.right;
} else {
return node.value;
}
}
return null;
}
测试代码：
public BSTTree1 createTree() {
/*
4
/ \
2 6
/ \ / \
1 3 5 7
*/
BSTTree1.BSTNode n1 = new BSTTree1.BSTNode(1, "张无忌");
BSTTree1.BSTNode n3 = new BSTTree1.BSTNode(3, "宋青书");
BSTTree1.BSTNode n2 = new BSTTree1.BSTNode(2, "周芷若", n1, n3);
BSTTree1.BSTNode n5 = new BSTTree1.BSTNode(5, "说不得");
BSTTree1.BSTNode n7 = new BSTTree1.BSTNode(7, "殷离");
BSTTree1.BSTNode n6 = new BSTTree1.BSTNode(6, "赵敏", n5, n7);
BSTTree1.BSTNode root = new BSTTree1.BSTNode(4, "小昭", n2, n6);
BSTTree1 tree = new BSTTree1();
tree.root = root;
return tree;
}
@Test
void get() {
BSTTree1 tree = createTree();
assertEquals("张无忌", tree.get(1));
assertEquals("周芷若", tree.get(2));
assertEquals("宋青书", tree.get(3));
assertEquals("小昭", tree.get(4));
assertEquals("说不得", tree.get(5));
assertEquals("赵敏", tree.get(6));
assertEquals("殷离", tree.get(7));
assertNull(tree.get(8));
}
1.4 Comparable
如果希望让除 int 外更多的类型能够作为 key，一种方式是 key 必须实现 Comparable 接口。
BSTTree2<K extends Comparable<K>, V>
/**
* 二叉搜索树, 泛型 key 版本
*/
public class BSTTree2<K extends Comparable<K>, V> {
static class BSTNode<K, V> {
K key;
V value;
BSTNode<K, V> left;
BSTNode<K, V> right;
public BSTNode(K key) {
this.key = key;
}
public BSTNode(K key, V value) {
this.key = key;
this.value = value;
}
public BSTNode(K key, V value, BSTNode<K, V> left, BSTNode<K, V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
BSTNode<K, V> root;
public V get(K key) {
BSTNode<K, V> p = root;
while (p != null) {
/*
-1 key < p.key
0 key == p.key
1 key > p.key
*/
int result = key.compareTo(p.key);
if (result < 0) {
p = p.left;
} else if (result > 0) {
p = p.right;
} else {
return p.value;
}
}
return null;
}
}
还有一种做法不要求 key 实现
Comparable接口，而是在构造 Tree 时把比较规则作为Comparator传入，将来比较 key 大小时都调用此Comparator进行比较，这种做法可以参考 Java 中的 java.util.TreeMap
PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
1.5 最值
1.5.1 最小值
递归实现
/**
* 任意节点为 根节点 所在的树的 最小值
*/
public Object min(BSTNode node) {
// return doMin(root);
return doMin(node);
}
public Object doMin(BSTNode node) {
if (node == null) {
return null;
}
// 左边已走到头
if (node.left == null) {
return node.value;
}
return doMin(node.left);
}
非递归实现
/**
* 任意节点为 根节点 所在的树的 最小值
*/
private Object min(BSTNode node) {
if (node == null) {
return null;
}
BSTNode p = node;
// 左边未走到头
while (p.left != null) {
p = p.left;
}
return p.value;
}
1.5.2 最大值
递归实现
/**
* 任意节点为 根节点 所在的树的 最大值
*/
public Object max(BSTNode node) {
return doMax(node);
}
public Object doMax(BSTNode node) {
if (node == null) {
return null;
}
// 右边已走到头
if (node.right == null) {
return node.value;
}
return doMax(node.right);
}
非递归实现
/**
* 任意节点为 根节点 所在的树的 最大值
*/
private Object max(BSTNode node) {
if (node == null) {
return null;
}
BSTNode p = node;
// 右边未走到头
while (p.right != null) {
p = p.right;
}
return p.value;
}
1.6 新增
力扣相似题目：701. 二叉搜索树中的插入操作
非递归实现
/**
* 插入 非递归实现
* @param key
* @param value
*/
public void put1(int key, Object value) {
BSTNode node = root;
// 当 新增时，需要记录父节点
BSTNode parent = null;
while(node != null) {
// 先记录，再进行下面的赋值操作
parent = node;
if (key < node.key) {
node = node.left;
} else if(node.key < key) {
node = node.right;
} else {
// 原本已有，更新
node.value = value;
return;
}
}
// 考虑树初始时，parent == null
if (parent == null) {
// 成为根节点
root = new BSTNode(key, value);
return;
}
// 原本没有，新增
if (parent.key < key) {
parent.right = new BSTNode(key, value);
} else { // 不可能相等，上面已经排除过
parent.left = new BSTNode(key, value);
}
}
递归实现（经典）
/**
* <h3>存储关键字和对应值</h3>
*
* @param key 关键字
* @param value 值
*
* 1. key 有 更新
* 2. key 没有 新增
*/
public void put(int key, Object value) {
root = doPut(root, key, value);
}
private BSTNode doPut(BSTNode node, int key, Object value) {
if (node == null) {
return new BSTNode(key, value);
}
if (key < node.key) {
node.left = doPut(node.left, key, value);
} else if (node.key < key) {
node.right = doPut(node.right, key, value);
} else {
node.value = value;
}
return node;
}
- 若找到 key，走 else 更新找到节点的值
- 若没找到 key，走第一个 if，创建并返回新节点
- 返回的新节点，作为上次递归时 node 的左孩子或右孩子
- 缺点是，会有很多不必要的赋值操作
1.7 前驱后继
一个节点的前驱（前任）节点是指比它小的节点中，最大的那个
一个节点的后继（后任）节点是指比它大的节点中，最小的那个
类似于把上面的数据节点向下平移到数轴 后的前后关系
例如上图中
- 1 没有前驱，后继是 2
- 2 前驱是 1，后继是 3
- 3 前驱是 2，后继是 4
- ...
简单的办法是中序遍历，即可获得排序结果，此时很容易找到前驱后继（效率不高）
要效率更高，需要研究一下规律，找前驱分成 2 种情况：
- 节点有左子树，此时前驱节点就是左子树的最大值，图中属于这种情况的有
- 2 的前驱是1
- 4 的前驱是 3
- 6 的前驱是 5
- 7 的前驱是 6
- 节点没有左子树，若离它最近的祖先（父节点，爷爷节点...）自左而来，此祖先即为前驱，如
- 3 的祖先 （祖先2，4）2 自左而来，前驱 2
- 5 的祖先（祖先6，7，4） 4 自左而来，前驱 4
- 8 的祖先（祖先4，7） 7 自左而来，前驱 7
- 1 没有这样的祖先，前驱 null
/**
* <h3>查找关键字的前任值</h3>
* 前任，比它小的所有值 中 最大的
* @param key 关键字
* @return 前任值
*/
public Object predecessor(int key) {
BSTNode p = root;
BSTNode ancestorFromLeft = null;
// 类似与get 先找到节点
while (p != null) {
if (key < p.key) {
p = p.left;
} else if (p.key < key) {
// 自左而来
ancestorFromLeft = p;
p = p.right;
} else {
// 找到节点
break;
}
}
// 没找到节点
if (p == null) {
return null;
}
// 找到节点 情况1：节点有左子树，此时前任就是左子树的最大值
if (p.left != null) {
return max(p.left);
}
// 找到节点 情况2：节点没有左子树，若离它最近的、自左而来的祖先就是前任
return ancestorFromLeft != null ?
ancestorFromLeft.value : null;
}
找后继也分成 2 种情况：
- 节点有右子树，此时后继节点即为右子树的最小值，如
- 2 的后继 3
- 3 的后继 4
- 5 的后继 6
- 7 的后继 8
- 节点没有右子树，若离它最近的祖先从右而来，此祖先即为后继，如
- 1 的祖先 2 自右而来，后继 2
- 4 的祖先 5 自右而来，后继 5
- 6 的祖先 7 自右而来，后继 7
- 8 没有这样的祖先，后继 null
/**
* <h3>查找关键字的后任值</h3>
* 后任，比它大的所有值 中 最小的
* @param key 关键字
* @return 后任值
*/
public Object successor(int key) {
BSTNode p = root;
BSTNode ancestorFromRight = null;
while (p != null) {
if (key < p.key) {
ancestorFromRight = p;
p = p.left;
} else if (p.key < key) {
p = p.right;
} else {
break;
}
}
// 没找到节点
if (p == null) {
return null;
}
// 找到节点 情况1：节点有右子树，此时后任就是右子树的最小值
if (p.right != null) {
return min(p.right);
}
// 找到节点 情况2：节点没有右子树，若离它最近的、自右而来的祖先就是后任
return ancestorFromRight != null ?
ancestorFromRight.value : null;
}
1.8 删除
相关例题：450. 删除二叉搜索树中的节点
四种情况：
要删除某节点（称为 D），必须先找到被删除节点的父节点，这里称为 Parent
- 删除节点没有左孩子，将右孩子托孤给
Parent - 删除节点没有右孩子，将左孩子托孤给
Parent - 删除节点左右孩子都没有，已经被涵盖在情况1、情况2 当中，把 null 托孤给
Parent - 删除节点左右孩子都有，可以将它的后继节点（称为 S）托孤给 Parent，设 S 的父亲为 SP，又分两种情况
- SP 就是被删除节点，此时 D （被删节点）与 S 紧邻，只需将 S 托孤给
Parent(以下图删除节点【4】为例：将【5】顶替【4】就行)
- SP 不是被删除节点，此时 D 与 S 不相邻，此时需要将 S 的后代托孤给 SP，再将 S 托孤给 Parent(以下图删除节点【4】为例：将【5】后代【6】交给其父节点【7】，然后再使【5】顶替【4】)
- SP 就是被删除节点，此时 D （被删节点）与 S 紧邻，只需将 S 托孤给
非递归实现：
/**
* <h3>根据关键字删除</h3>
*
* @param key 关键字
* @return 被删除关键字对应值
*/
public Object remove(int key) {
BSTNode p = root;
BSTNode parent = null;
// 查找节点，及其 父节点
while (p != null) {
if (key < p.key) {
parent = p;
p = p.left;
} else if (p.key < key) {
parent = p;
p = p.right;
} else {
break;
}
}
// 没找到节点
if (p == null) {
return null;
}
// 删除操作
if (p.left == null) {
shift(parent, p, p.right); // 情况1 对情况3（左右null）通用
} else if (p.right == null) {
shift(parent, p, p.left); // 情况2
} else { // 左右孩子都有
// 情况4
// 4.1 被删除节点找后继 和 后继节点其父亲
BSTNode s = p.right;
BSTNode sParent = p; // 后继节点的 父亲
while (s.left != null) {
sParent = s;
s = s.left;
}
// 后继节点即为 s
if (sParent != p) { // 不相邻 后继节点的父节点不是被删除元素
// 4.2 删除和后继不相邻, 处理后继的后事
shift(sParent, s, s.right); // 不可能有左孩子 前面while中 s.left == null
s.right = p.right; // 右子树发生变化，而且shift只会修改parent的指针指向
}
// 4.3 后继取代被删除节点 （如果相邻，直接走这步）
shift(parent, p, s);
s.left = p.left; // shift只会修改parent的指针指向
}
return p.value;
}
/**
* 托孤方法
*
* @param parent 被删除节点的父亲
* @param deleted 被删除节点
* @param child 被顶上去的节点
*/
private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
if (parent == null) {
root = child; // root节点被删，child变根节点
} else if (deleted == parent.left) { // 被删除节点来自 父的左边，则左边
parent.left = child;
} else {
parent.right = child;
}
}
递归版本：
/**
* <h3>根据关键字删除</h3>
*
* @param key 关键字
* @return 被删除关键字对应值
*/
public Object remove(int key) {
ArrayList<Object> result = new ArrayList<>(); // 保存被删除节点的值
root = doRemove(root, key, result);
return result.isEmpty() ? null : result.get(0);
}
/*
4
/ \
2 6
/ \
1 7
node 起点
返回值 删剩下的孩子(找到) 或 null(没找到)
*/
private BSTNode doRemove(BSTNode node, int key, ArrayList<Object> result) {
if (node == null) {
return null;
}
if (key < node.key) {
node.left = doRemove(node.left, key, result);
return node;
}
if (node.key < key) {
node.right = doRemove(node.right, key, result);
return node;
}
result.add(node.value);
if (node.left == null) { // 情况1 - 只有右孩子
return node.right;
}
if (node.right == null) { // 情况2 - 只有左孩子
return node.left;
}
BSTNode s = node.right; // 情况3 - 有两个孩子 查找后继节点
while (s.left != null) {
s = s.left;
}
// 【s是后继节点，node是被删除节点】
// 通过删除自己，使后继节点原有的右子树交给其父母
// 删除后继节点不需要add value
s.right = doRemove(node.right, s.key, new ArrayList<>());
// 注意顺序， 先删除再赋值 s.left
s.left = node.left;
return s;
/*
if (node.left != null && node.right != null) {
BSTNode s = node.right;
while (s.left != null) {
s = s.left;
}
s.right = doDelete(node.right, s.key, new ArrayList<>());
s.left = node.left;
return s;
}
return node.left != null ? node.left : node.right;
*/
}
说明
ArrayList<Object> result用来保存被删除节点的值- 第二、第三个 if 对应没找到的情况，继续递归查找和删除，注意后续的
doDelete返回值代表删剩下的，因此需要更新 - （被注释的迭代代码）最后一个 return 对应删除节点只有一个孩子的情况，返回那个不为空的孩子，待删节点自己因没有返回而被删除
- 第四个 if 对应删除节点有两个孩子的情况，此时需要找到后继节点，并在待删除节点的右子树中删掉后继节点，最后用后继节点替代掉待删除节点返回，别忘了改变后继节点的左右指针
1.9 范围查询
核心：中序遍历
1.9.1 小于
使用中序遍历
/*
4
/ \
2 6
/ \ / \
1 3 5 7
*/
// 找 < key 的所有 value 中序遍历就是按顺序的
public List<Object> less(int key) { // key=6
ArrayList<Object> result = new ArrayList<>();
BSTNode p = root;
LinkedList<BSTNode> stack = new LinkedList<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
BSTNode pop = stack.pop();
// 处理值
if (pop.key < key) {
result.add(pop.value);
} else {
break;
}
p = pop.right;
}
}
return result;
}
1.9.2 大于
public List<Object> greater(int key) {
ArrayList<Object> result = new ArrayList<>();
BSTNode p = root;
LinkedList<BSTNode> stack = new LinkedList<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
BSTNode pop = stack.pop();
if (pop.key > key) {
result.add(pop.value);
}
p = pop.right;
}
}
return result;
}
但这样效率不高，可以用 RNL （右-值-左）（反向中序遍历）遍历
注：
- Pre-order, NLR
- In-order, LNR
- Post-order, LRN
- Reverse pre-order, NRL
- Reverse in-order, RNL
- Reverse post-order, RLN
// 找 > key 的所有 value
public List<Object> greater(int key) {
/*ArrayList<Object> result = new ArrayList<>();
BSTNode p = root;
LinkedList<BSTNode> stack = new LinkedList<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
BSTNode pop = stack.pop();
// 处理值
if (pop.key > key) {
result.add(pop.value);
}
p = pop.right;
}
}
return result;*/
ArrayList<Object> result = new ArrayList<>();
BSTNode p = root;
LinkedList<BSTNode> stack = new LinkedList<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.right; // 反向
} else {
BSTNode pop = stack.pop();
// 处理值
if (pop.key > key) {
result.add(pop.value);
} else {
break;
}
p = pop.left;
}
}
return result;
}
1.9.3 区间
// 找 >= key1 且 <= key2 的所有值
public List<Object> between(int key1, int key2) {
ArrayList<Object> result = new ArrayList<>();
BSTNode p = root;
LinkedList<BSTNode> stack = new LinkedList<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
BSTNode pop = stack.pop();
// 处理值
if (pop.key >= key1 && pop.key <= key2) {
result.add(pop.value);
} else if (pop.key > key2) {
break;
}
p = pop.right;
}
}
return result;
}
1.10 小结
优点：
- 如果每个节点的左子树和右子树的大小差距不超过一，可以保证搜索操作的时间复杂度是
O(log n)，效率高。 - 插入、删除结点等操作也比较容易实现，效率也比较高。
- 对于有序数据的查询和处理，二叉查找树非常适用，可以使用中序遍历得到有序序列。
缺点：
- 如果输入的数据是有序或者近似有序的，就会出现极度不平衡的情况，可能导致搜索效率下降，时间复杂度退化成
O(n)。 - 对于频繁地插入、删除操作，需要维护平衡二叉查找树，例如红黑树、AVL 树等，否则搜索效率也会下降。
- 对于存在大量重复数据的情况，需要做相应的处理，否则会导致树的深度增加，搜索效率下降。
- 对于结点过多的情况，由于树的空间开销较大，可能导致内存消耗过大，不适合对内存要求高的场景。
1.11 例题
1.11.1 验证二叉搜索树
给你一个二叉树的根节点
root，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
方法一：中序非递归实现
public boolean isValidBST(TreeNode root) {
TreeNode p = root;
LinkedList<TreeNode> stack = new LinkedList<>();
long prev = Long.MIN_VALUE;
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode pop = stack.pop();
if (prev >= pop.val) {
return false;
}
prev = pop.val;
p = pop.right;
}
}
return true;
}
- 记录
prev需要用long，否则若测试用例中最小的节点为Integer.MIN_VALUE则测试会失败 - 注意，如果相邻两个节点相等，也不应当通过测试，例如，下面的树也是不合法的
2
/
2
方法二：中序递归（全局变量）
// 解法2. 中序遍历递归实现(全局变量记录 prev) 0ms
long prev = Long.MIN_VALUE;
public boolean isValidBST2(TreeNode node) {
if (node == null) {
return true;
}
boolean a = isValidBST2(node.left);
if (!a) {
return false;
}
if (prev >= node.val) {
return false;
}
prev = node.val;
return isValidBST2(node.right);
}
方法三：中序遍历（局部变量）
// 解法3. 中序遍历递归实现(局部变量记录 prev) 0ms
public boolean isValidBST3(TreeNode node) {
return doValid3(node, new AtomicLong(Long.MIN_VALUE));
}
private boolean doValid3(TreeNode node, AtomicLong prev) {
if (node == null) {
return true;
}
// 判断左子树
// 左子树走到头
boolean a = doValid3(node.left, prev);
// 有问题直接返回false,不用判断右子树
if (!a) {
return false;
}
// 判断当前节点值
if (prev.get() >= node.val) {
return false;
}
prev.set(node.val);
// 判断右子树
return doValid3(node.right, prev);
}
- 为何不能用 Long 或 long？因为它们都是局部变量且不可变，因此每次赋值时，并不会改变其它方法调用时的新设置的
prev值- 在执行下面时，会错误显示
true
- 在执行下面时，会错误显示
3
\
4
/
5
方法四：上下限 递归
// 解法4. 上下限递归实现 0ms
public boolean isValidBST(TreeNode node) {
return doValid4(node, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean doValid4(TreeNode node, long min, long max){
if (node == null) {
return true;
}
if (node.val <= min || node.val >= max) {
return false;
}
// 判断左右孩子是否合法
return doValid4(node.left, min, node.val) // 左孩子 上限是node（父节点）
&& doValid4(node.right, node.val, max); // 右孩子 下限是node（父节点）
}
1.11.2 求范围和
给定二叉搜索树的根结点
root，返回值位于范围[low, high]之间的所有结点的值的和。
方法一：中序非递归
// 解法1. 中序遍历非递归实现 4ms
public int rangeSumBST(TreeNode node, int low, int high) {
TreeNode p = node;
LinkedList<TreeNode> stack = new LinkedList<>();
int sum = 0;
while(p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode pop = stack.pop();
// 处理值 遇到大于的值可以直接break，避免继续遍历
if (pop.val > high) {
break;
}
if (pop.val >= low) {
sum += pop.val;
}
p = pop.right;
}
}
return sum;
}
- 使用
LinkedList<>，leedcode 执行耗时4ms - 使用
Stack<>，leedcode 执行耗时17ms，没有if (pop.val > high) break;则27ms。
方法二：中序递归
// 1ms
public int rangeSumBST(TreeNode node, int low, int high) {
if (node == null) {
return 0;
}
int a = rangeSumBST(node.left, low, high); // 左
int b = 0;
if (node.val >= low && node.val <= high) { // 中
b = node.val;
}
return a + b + rangeSumBST(node.right, low, high); // 右
}
方法三：上下限递归
// 上下限递归 0ms
public int rangeSumBST(TreeNode node, int low, int high) {
if (node == null) {
return 0;
}
if (node.val < low) {
return rangeSumBST(node.right, low, high);
}
if (node.val > high) {
return rangeSumBST(node.left, low, high);
}
// 在范围内
return node.val + rangeSumBST(node.left, low, high) + rangeSumBST(node.right, low, high);
}
- node.val < low 只需考虑它右子树的累加结果。（节点小于low，它的左子树肯定都小于，因此不用考虑，下面同理）
- node.val > high 只需考虑它左子树的累加结果
- node.val 在范围内，需要把当前节点的值加上其左右子树的累加结果
1.11.3 前序遍历构造二叉搜索树
给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。(与之前二叉树不一样，这个具有严格的左右关系)
preorder中的值 互不相同
输入：preorder = [8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]
输入: preorder = [1,3]
输出: [1,null,3]
方法一：直接插入（递归）
public TreeNode bstFromPreorder(int[] preorder) {
TreeNode root = insert(null, preorder[0]);
for (int i = 1; i < preorder.length; i++) {
insert(root, preorder[i]);
}
return root;
}
private TreeNode insert(TreeNode node, int val) {
if (node == null) {
return new TreeNode(val);
}
if(val < node.val) {
node.left = insert(node.left, val);
} else if(node.val < val){
node.right = insert(node.right, val);
}
return node;
}
方法二：上限法
public TreeNode bstFromPreorder(int[] preorder) {
return insert(preorder, Integer.MAX_VALUE);
}
// 全局变量
int i = 0;
/*
依次处理preorder 中的每个值，返回创建好的节点或null
1. 如果超过上限，返回null，作为孩子返回
2. 如果没有超过上限，创建节点，并设置左右孩子，左右孩子完整后返回
*/
private TreeNode insert(int[] preorder, int max) {
if (i == preorder.length) { // 结束条件
return null;
}
int val = preorder[i];
System.out.println(val + String.format("[%d]", max));
if (val > max) {
return null;
}
// 如果没有超过上限，创建节点
TreeNode node = new TreeNode(val);
i++;
// 判断数组后面数据能否成为 其左右孩子，要么是递归后的node，要么是null
node.left = insert(preorder, node.val);
node.right = insert(preorder, max); // 保持上限不变
return node;
}
依次处理 prevorder 中每个值, 返回创建好的节点或 null 作为上个节点的孩子
- 如果超过上限，返回
null - 如果没超过上限，创建节点，并将其左右孩子设置完整后返回
i++需要放在设置左右孩子之前，意思是从剩下的元素中挑选左右孩子
- 时间复杂度：
O(N)，这里N是输入数组的长度。
方法三：分治法
举例：中序遍历结果：[ 8, 5, 1, 7, 10, 12]
- 刚开始 8, 5, 1, 7, 10, 12，方法每次执行，确定本次的根节点和左右子树的分界线
- 第一次确定根节点为 8，比8小的为左子树 5, 1, 7，比8大的为右子树 10, 12
- 对 5, 1, 7 做递归操作，确定根节点是 5， 左子树是 1， 右子树是 7
- 对 1 做递归操作，确定根节点是 1，左右子树为 null
- 对 7 做递归操作，确定根节点是 7，左右子树为 null
- 对 10, 12 做递归操作，确定根节点是 10，左子树为 null，右子树为 12
- 对 12 做递归操作，确定根节点是 12，左右子树为 null
- 递归结束，返回本范围内的根节点
public TreeNode bstFromPreorder(int[] preorder) {
return partition(preorder, 0, preorder.length - 1);
}
private TreeNode partition(int[] preorder, int start, int end) {
if (start > end) {
return null;
}
// 根节点
TreeNode root = new TreeNode(preorder[start]);
int index = start + 1;
while (index <= end) {
if (preorder[index] > preorder[start]) {
break;
}
index++;
}
// index 就是右子树的起点
root.left = partition(preorder, start + 1, index - 1);
root.right = partition(preorder, index, end);
return root;
}
时间复杂度：
O(NlogN)
1.11.4 二叉搜索树的最近公共祖先
给定一个二叉搜索树，找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
要点：若 p，q 在 ancestor 的两侧，则 ancestor 就是它们的最近公共祖先
/*
__ 6 __
/ \
2 8
/ \ / \
0 4 7 9
/ \
3 5
待查找节点 p q 在某一节点(node)的两侧(一个>node.val, 一个<node.val)，那么此节点就是最近的公共祖先
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode a = root;
while (p.val < a.val && q.val < a.val || a.val < p.val && a.val < q.val) { // 在同一侧
if (p.val < a.val) { // 都在左侧
a = a.left;
} else {
a = a.right;
}
}
return a;
}
其它题目
| 题号 | 名称 |
|---|---|
| Leetcode 236 | 二叉树的最近公共祖先 |
| Leetcode 114 | 二叉树展开为链表 |
| Leetcode 108 | 有序数组构造平衡二叉搜索树 |
| Leetcode 1382 | 二叉搜索树变为平衡 |
2. avl树
2.1 概述
AVL 树是一种自平衡二叉搜索树，由托尔·哈斯特罗姆在 1960 年提出并在 1962 年发表。它的名字来源于发明者的名字：Adelson-Velsky 和 Landis，他们是苏联数学家，于 1962 年发表了一篇论文，详细介绍了 AVL 树的概念和性质。
在二叉搜索树中，如果插入的元素按照特定的顺序排列，可能会导致树变得非常不平衡，从而降低搜索、插入和删除的效率。为了解决这个问题，AVL 树通过在每个节点中维护一个平衡因子来确保树的平衡。平衡因子是左子树的高度减去右子树的高度。如果平衡因子的绝对值大于等于 2，则通过旋转操作来重新平衡树。
AVL 树是用于存储有序数据的一种重要数据结构，它是二叉搜索树的一种改进和扩展。它不仅能够提高搜索、插入和删除操作的效率，而且还能够确保树的深度始终保持在
O(log n)的水平。随着计算机技术的不断发展，AVL 树已经成为了许多高效算法和系统中必不可少的一种基础数据结构。
- 如果一棵二叉搜索树长的不平衡，那么查询的效率会受到影响，如下图
- 通过旋转可以让树重新变得平衡，并且不会改变二叉搜索树的性质（即左边仍然小，右边仍然大）以节点3为支点，进行右旋：
如何判断失衡？
如果一个节点的左右孩子，高度差超过 1，则此节点失衡，才需要旋转
2.2 节点类
/**
* <h3>AVL 树</h3>
* <ul>
* <li>二叉搜索树在插入和删除时，节点可能失衡</li>
* <li>如果在插入和删除时通过旋转, 始终让二叉搜索树保持平衡, 称为自平衡的二叉搜索树</li>
* <li>AVL 是自平衡二叉搜索树的实现之一</li>
* </ul>
*/
static class AVLNode {
int key;
Object value;
AVLNode left;
AVLNode right;
int height = 1; // 高度 新增或删除时及时更
public AVLNode(int key, Object value) {
this.key = key;
this.value = value;
}
public AVLNode(int key) {
this.key = key;
}
public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
2.3 高度代码
节点可能为null，因此不可能出现
null.height，所以使用方法
求高度代码
height 函数方便求节点为 null 时的高度
// 求节点的高度
private int height(AVLNode node) {
return node == null ? 0 : node.height;
}
更新高度代码
将来新增、删除、旋转时，高度都可能发生变化，需要更新。
类似于前面的例题，二叉树的最大深度，高度为左右子树的最大值+1
// 更新节点高度 (新增、删除、旋转)
private void updateHeight(AVLNode node) {
node.height = Integer.max(height(node.left), height(node.right)) + 1;
}
2.4 平衡因子
何时触发失衡判断？
定义平衡因子（balance factor）如下
平衡因子左子树高度右子树高度
当平衡因子：
- bf = 0，1，-1 时，表示左右平衡
- bf > 1 时，表示左边太高
- bf < -1 时，表示右边太高
对应代码
// 平衡因子 (balance factor) = 左子树高度-右子树高度 1 -1 0
private int bf(AVLNode node) {
return height(node.left) - height(node.right);
}
2.5 失衡的四种情况
LL
- 失衡节点（图中 8 红色）的 bf > 1，即左边更高
- 失衡节点的左孩子（图中 6）的 bf >= 0 即左孩子这边也是左边更高或等高
- 解决：右旋一次
LR
- 失衡节点（图中 8）的 bf > 1，即左边更高
- 失衡节点的左孩子（图中 6 红色）的 bf < 0 即左孩子这边是右边更高
- 解决：左子树先左旋，变成LL，根节点再右旋
对称的还有两种情况：
RL
- 失衡节点（图中 3）的 bf <-1，即右边更高
- 失衡节点的右孩子（图中 6 红色）的 bf > 0，即右孩子这边左边更高
- 解决：右子树先右旋，变成RR，根节点再左旋
RR
- 失衡节点（图中 3）的 bf <-1，即右边更高
- 失衡节点的右孩子（图中 6 红色）的 bf <= 0，即右孩子这边右边更高或等高
- 解决：左旋一次
2.6 旋转
解决失衡
失衡可以通过树的旋转解决。树的旋转是在不干扰元素顺序的情况下更改结构，通常用来让树的高度变得平衡。
观察下面一棵二叉搜索树，可以看到，旋转后，并未改变树的左小右大特性，但根、父、孩子节点都发生了变化
4 2
/ \ 4 right / \
2 5 --------------------> 1 4
/ \ <-------------------- / \
1 3 2 left 3 5
2.6.1 右旋
旋转前
- 红色节点，旧根（失衡节点）
- 黄色节点，旧根的左孩子，将来作为新根，旧根是它右孩子
- 绿色节点，新根的右孩子，将来要换爹作为旧根的左孩子
旋转后
代码
// 更新red yellow高度 有顺序！！！
// 旋转后，红色节点在下面，黄色在上面，先更新底部的数据（递归）
// 参数：要旋转的节点, 返回值：新的根节点
private AVLNode rightRotate(AVLNode red) {
AVLNode yellow = red.left;
AVLNode green = yellow.right;
yellow.right = red; // 上位
red.left = green; // 换爹
// 更新red yellow高度 有顺序！！！
// 旋转后，红色节点在下面，黄色在上面，先更新底部的数据（递归）
updateHeight(red);
updateHeight(yellow);
return yellow;
}
2.6.2 左旋
旋转前
- 红色节点，旧根（失衡节点）
- 黄色节点，旧根的右孩子，将来作为新根，旧根是它左孩子
- 绿色节点，新根的左孩子，将来要换爹作为旧根的右孩子
旋转后
代码
// 参数：要旋转的节点, 返回值：新的根节点
private AVLNode leftRotate(AVLNode red) {
AVLNode yellow = red.right;
AVLNode green = yellow.left;
yellow.left = red;
red.right = green;
updateHeight(red);
updateHeight(yellow);
return yellow;
}
2.6.3 左右旋
指先左旋左子树，再右旋根节点（失衡），这时一次旋转并不能解决失衡
左子树旋转后
根右旋前
根右旋后
代码
// 先左旋左子树, 再右旋根节点
private AVLNode leftRightRotate(AVLNode node) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
2.6.4 右左旋
指先右旋右子树，再左旋根节点（失衡）
右子树右旋后
根左旋前
根左旋后
代码
// 先右旋右子树, 再左旋根节点
private AVLNode rightLeftRotate(AVLNode node) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
2.7 检查失衡及调整
// 检查节点是否失衡, 重新平衡代码
private AVLNode balance(AVLNode node) {
if (node == null) {
return null;
}
int bf = bf(node);
if (bf > 1 && bf(node.left) >= 0) { // LL
return rightRotate(node);
} else if (bf > 1 && bf(node.left) < 0) { // LR
return leftRightRotate(node);
} else if (bf < -1 && bf(node.right) > 0) { // RL
return rightLeftRotate(node);
} else if (bf < -1 && bf(node.right) <= 0) { // RR
return leftRotate(node);
}
return node;
}
以上四种旋转代码里，都需要更新高度，需要更新的节点是红色、黄色，而绿色节点高度不变
2.8 新增
递归实现：
AVLNode root;
public void put(int key, Object value) {
// 返回的是 新的 根节点
root = doPut(root, key, value);
}
private AVLNode doPut(AVLNode node, int key, Object value) {
// 1. 找到空位, 创建新节点
if (node == null) {
// 新增节点直接return，不用更新 新节点的高度及balance
return new AVLNode(key, value);
}
// 2. key 已存在, 更新
if (key == node.key) {
node.value = value;
return node;
}
// 3. 继续查找
if (key < node.key) {
node.left = doPut(node.left, key, value); // 向左
} else {
node.right = doPut(node.right, key, value); // 向右
}
updateHeight(node); // 更新高度
return balance(node); // 检查平衡
}
2.9 删除
public void remove(int key) {
root = doRemove(root, key);
}
private AVLNode doRemove(AVLNode node, int key) {
// 1. node == null
if (node == null) {
return null;
}
// 2. 没找到 key -> 递归查找
if (key < node.key) {
node.left = doRemove(node.left, key);
} else if (node.key < key) {
node.right = doRemove(node.right, key);
} else {
// 3. 找到 key 1) 没有孩子 2) 只有一个孩子 3) 有两个孩子
if (node.left == null && node.right == null) {
return null; // 没有孩子，删掉后就剩null了
} else if (node.left == null) {
node = node.right; // 向下执行，更新高度 及 平衡
} else if (node.right == null) {
node = node.left;
} else {
AVLNode s = node.right; // 找后继节点
while (s.left != null) {
s = s.left;
}
// s 后继节点
s.right = doRemove(node.right, s.key);
s.left = node.left;
node = s;
}
}
// 4. 更新高度
updateHeight(node);
// 5. balance
return balance(node);
}
2.10 小结
AVL树的优点：
- AVL树是一种自平衡树，保证了树的高度平衡，从而保证了树的查询和插入操作的时间复杂度均为
O(logn)。 - 相比于一般二叉搜索树，AVL树对查询效率的提升更为显著，因为其左右子树高度的差值不会超过1，避免了二叉搜索树退化为链表的情况，使得整棵树的高度更低。
- AVL树的删除操作比较简单，只需要像插入一样旋转即可，在旋转过程中树的平衡性可以得到维护。
AVL树的缺点：
- AVL树每次插入或删除节点时需要进行旋转操作，这个操作比较耗时，因此在一些应用中不太适用。
- 在AVL树进行插入或删除操作时，为保持树的平衡需要不断进行旋转操作，在一些高并发环节和大数据量环境下，这可能会导致多余的写锁导致性能瓶颈。
- AVL树的旋转操作相对较多，因此在一些应用中可能会造成较大的空间浪费。
3. 红黑树
3.1 概述
红黑树是一种自平衡二叉查找树，最早由一位名叫Rudolf Bayer的德国计算机科学家于1972年发明。然而，最初的树形结构不是现在的红黑树，而是一种称为B树的结构，它是一种多叉树，可用于在磁盘上存储大量数据。
在1980年代早期，计算机科学家Leonard Adleman和Daniel Sleator推广了红黑树，并证明了它的自平衡性和高效性。从那时起，红黑树成为了最流行的自平衡二叉查找树之一，并被广泛应用于许多领域，如编译器、操作系统、数据库等。
红黑树的名字来源于红色节点和黑色节点的交替出现，它们的颜色是用来维护树的平衡性的关键。它们的颜色具有特殊的意义，黑色节点代表普通节点，而红色节点代表一个新添加的节点，它们必须满足一些特定的规则才能维持树的平衡性。
- 红黑树也是一种自平衡的二叉搜索树，较之 AVL，插入和删除时旋转次数更少
3.2 红黑树特性
- 所有节点都有两种颜色：红🔴、黑⚫️
- 所有
null视为黑色⚫️ - 红色🔴节点不能相邻
- 根节点是黑色⚫️
- 从根到任意一个叶子节点，路径中的黑色⚫️节点数一样
以下不算红黑树：
因为 null 节点视为黑色，所以实际情况如下：（其黑色不平衡）
3.3 节点类
// 枚举
enum Color {
RED, BLACK;
}
Node root;
static class Node {
int key;
Object value;
Node left;
Node right;
Node parent; // 父节点
Color color = Color.RED; // 颜色 （默认红色）
public Node(int key, Object value) {
this.key = key;
this.value = value;
}
public Node(int key) {
this.key = key;
}
public Node(int key, Color color) {
this.key = key;
this.color = color;
}
public Node(int key, Color color, Node left, Node right) {
this.key = key;
this.color = color;
this.left = left;
this.right = right;
if (left != null) {
left.parent = this;
}
if (right != null) {
right.parent = this;
}
}
// 是否是左孩子
boolean isLeftChild() {
return parent != null && parent.left == this;
}
// 叔叔
Node uncle() {
// 对应上面3.2图的
// 节点 8（根节点） 节点 5 10（父节点没有兄弟）
if (parent == null || parent.parent == null) {
return null;
}
// 父节点 是 爷爷节点的左孩子，那叔叔节点就是 爷爷节点的右孩子
if (parent.isLeftChild()) {
return parent.parent.right;
} else {
return parent.parent.left;
}
}
// 兄弟
Node sibling() {
// 根节点
if (parent == null) {
return null;
}
// 如果是父节点的左孩子，那么兄弟就是父节点的右孩子
if (this.isLeftChild()) {
return parent.right;
} else {
return parent.left;
}
}
}
3.4 判断及旋转方法
判断红黑：
// 避免 调用 node.color 时发生 null.color
// 判断红
boolean isRed(Node node) {
return node != null && node.color == Color.RED;
}
// 判断黑
boolean isBlack(Node node) {
// return !isRed(node);
// null 节点为黑色
return node == null || node.color == Color.BLACK;
}
右旋：
右旋前：
右旋后：
代码：
// 右旋 1. parent 的处理 2. 旋转后新根的父子关系
private void rightRotate(Node pink) {
Node parent = pink.parent;
Node yellow = pink.left;
Node green = yellow.right;
if (green != null) {
green.parent = pink;
}
yellow.right = pink;
yellow.parent = parent; // 黄色的父节点 变为 父节点的父节点
pink.left = green;
pink.parent = yellow;
// 更上层的父子关系
if (parent == null) { // node 原本为根节点
root = yellow; // 替换根节点
} else if (parent.left == pink) {
parent.left = yellow;
} else {
parent.right = yellow;
}
}
同理，左旋代码：
// 左旋
private void leftRotate(Node pink) {
Node parent = pink.parent;
Node yellow = pink.right;
Node green = yellow.left;
if (green != null) {
green.parent = pink;
}
yellow.left = pink;
yellow.parent = parent;
pink.right = green;
pink.parent = yellow;
if (parent == null) {
root = yellow;
} else if (parent.left == pink) {
parent.left = yellow;
} else {
parent.right = yellow;
}
}
3.5 插入
插入put方法代码：
/**
* 新增或更新
* <br>
* 正常增、遇到红红不平衡进行调整
*
* @param key 键
* @param value 值
*/
public void put(int key, Object value) {
// 查找空位
Node p = root;
Node parent = null;
while (p != null) {
parent = p; // 更新父节点
if (key < p.key) {
p = p.left;
} else if (p.key < key) {
p = p.right;
} else {
p.value = value; // （key已存在）更新
return;
}
}
Node inserted = new Node(key, value);
if (parent == null) { // 树中无节点
root = inserted;
} else if (key < parent.key) {
parent.left = inserted;
inserted.parent = parent;
} else {
parent.right = inserted;
inserted.parent = parent;
}
// 调整 红色 不平衡
fixRedRed(inserted);
}
插入的四种情况：
插入节点均视为红色🔴
case 1：插入节点为根节点，将根节点变黑⚫️
case 2：插入节点（默认红色）的父亲若为黑色⚫️，树的红黑性质不变，无需调整
插入节点的父亲为红色🔴，触发红红相邻
case 3：叔叔为红色🔴
- 父亲变为黑色⚫️，为了保证黑色平衡，连带的叔叔也变为黑色⚫️
- 祖父如果是黑色不变，会造成这颗子树黑色过多，因此祖父节点变为红色🔴
- 祖父如果变成红色，可能会接着触发红红相邻，因此对将祖父进行递归调整
举例：
刚插入新节点1️⃣后：
- 修改上面的红色节点2，变为黑色，叔叔节点4也变黑。但此时右侧树黑色不平衡
- 因此修改节点3为红色（祖父改红色），此时黑色平衡，但3，5都为红色，又是红红不平衡
- 同理，修改上面的红色节点5，将其改为黑色，叔叔节点13也改黑。祖父9改红色。
- 因为祖父9是根节点，再将其变为黑色。
插入后：
case 4：叔叔为黑色⚫️
- 父亲为左孩子，插入节点也是左孩子，此时即 LL 不平衡
- 让父亲变黑⚫️，为了保证这颗子树黑色不变，将祖父变成红🔴，但叔叔子树少了一个黑色
- 祖父右旋，补齐一个黑色给叔叔，父亲旋转上去取代祖父，由于它是黑色，不会再次触发红红相邻
举例： 插入节点2后：
- 节点3变黑色，此时黑色不平衡
- 祖父5变红色，但此时依旧黑色不平衡，与3.2的示例一样，根节点到5的右孩子（叶子节点）（null）的黑色节点少了一个，黑色不平衡。
- 此时右旋，结果如下图
总结：父亲变黑，祖父变红，祖父右旋
- 父亲为左孩子，插入节点是右孩子，此时即 LR 不平衡
- 父亲左旋，变成 LL 情况，按 1. 来后续处理
举例：插入节点4后：
- 节点3左旋，变为下图：
- 跟上面 case1 一样，变成 LL，后续按 case1 处理
- 靠上面的红色，即新插入的节点变黑色，其父亲节点5（原祖父节点变红色），然后祖父节点5右旋，结果如下：
- 父亲为右孩子，插入节点也是右孩子，此时即 RR 不平衡
- 让父亲变黑⚫️，为了保证这颗子树黑色不变，将祖父变成红🔴，但叔叔子树少了一个黑色
- 祖父左旋，补齐一个黑色给叔叔，父亲旋转上去取代祖父，由于它是黑色，不会再次触发红红相邻
- 父亲为右孩子，插入节点是左孩子，此时即 RL 不平衡
- 父亲右旋，变成 RR 情况，按 3. 来后续处理
代码如下：
void fixRedRed(Node x) {
// case 1 插入节点是根节点，变黑即可
if (x == root) {
x.color = Color.BLACK;
return;
}
// case 2 插入节点父亲是黑色，无需调整
if (isBlack(x.parent)) {
return;
}
/* case 3 当红红相邻，叔叔为红时
需要将父亲、叔叔变黑、祖父变红，然后对祖父做递归处理
*/
Node parent = x.parent;
Node uncle = x.uncle();
// 如果触发红红相邻，肯定有祖父 不为null，祖父至少为根节点黑色，下面两个红色父子
Node grandparent = parent.parent;
// ---叔叔红色---
if (isRed(uncle)) {
parent.color = Color.BLACK;
uncle.color = Color.BLACK;
grandparent.color = Color.RED;
fixRedRed(grandparent); // 递归调用，可以传递null
return;
}
// ---叔叔黑色---
// case 4 当红红相邻，叔叔为黑时
if (parent.isLeftChild() && x.isLeftChild()) { // LL
parent.color = Color.BLACK;
grandparent.color = Color.RED;
rightRotate(grandparent);
} else if (parent.isLeftChild()) { // LR
leftRotate(parent);
x.color = Color.BLACK;
grandparent.color = Color.RED;
rightRotate(grandparent);
} else if (!x.isLeftChild()) { // RR
parent.color = Color.BLACK;
grandparent.color = Color.RED;
leftRotate(grandparent); // 与LL旋转方向相反
} else { // RL
rightRotate(parent);
x.color = Color.BLACK;
grandparent.color = Color.RED;
leftRotate(grandparent);
}
}
3.6 删除
查找删除节点
// 查找删除节点
private Node find(int key) {
Node p = root;
while (p != null) {
if (key < p.key) {
p = p.left;
} else if (p.key < key) {
p = p.right;
} else {
return p;
}
}
return null;
}
查找剩余节点：(如果有两个孩子，返回删除节点的后继节点；只有一个孩子，返回孩子节点)
// 查找剩余节点
private Node findReplaced(Node deleted) {
if (deleted.left == null && deleted.right == null) {
return null;
}
if (deleted.left == null) {
return deleted.right;
}
if (deleted.right == null) {
return deleted.left;
}
// 左右孩子不为null
Node s = deleted.right;
while (s.left != null) {
s = s.left;
}
return s;
}
删除方法：
/**
* 删除
* <br>
* 正常删、会用到李代桃僵技巧、遇到黑黑不平衡进行调整
*
* @param key 键
*/
public void remove(int key) {
Node deleted = find(key);
if (deleted == null) {
return;
}
doRemove(deleted);
}
删除的几种情况
case0：如果删除节点有两个孩子
- 交换 删除节点和后继节点的 key，value，递归删除后继节点，直到该节点没有孩子或只剩一个孩子
举例：删除节点5
交换节点5与后继节点的键值，因为是后继节点，所以后继节点.left 肯定== null。要么没有孩子，要么只有一个右孩子。此时再调用删除方法，删除现在的 后继节点。
如果删除节点没有孩子或只剩一个孩子
case 1：删的是根节点
- 删完了，直接将 root = null
- 用剩余节点（孩子节点）替换了根节点的 key，value，根节点孩子 = null，颜色保持黑色⚫️不变
如果删除的根节点只有一个孩子，那他孩子肯定是红色，而且该孩子没有孩子，否则红色和黑色都不平衡。
删黑色会失衡，删红色不会失衡，但删黑色有一种简单情况
case 2：删的是黑⚫️，剩下的是红🔴，剩下这个红节点变黑⚫️（少了一个黑色，但是补了一个黑色上去）
删除节点和剩下节点都是黑⚫️，触发双黑，双黑意思是，少了一个黑
case 3：被调整节点的兄弟为红🔴，此时两个侄子定为黑 ⚫️
以删除节点4为例：
- 删除节点是左孩子，父亲左旋
此时黑色不平衡，8（兄弟）变黑色，6（父亲）变红色
- 删除节点是右孩子，父亲右旋
- 父亲和兄弟要变色，保证旋转后颜色平衡
- 旋转的目的是让黑侄子变为删除节点的黑兄弟，对删除节点再次递归，进入 case 4 或 case 5
case 4：被调整节点的兄弟为黑⚫️，两个侄子都为黑 ⚫️
- 将兄弟变红🔴，目的是将删除节点和兄弟那边的黑色高度同时减少 1如图，删除3，将节点7变红。
- 如果父亲是红🔴，则需将父亲变为黑，避免红红，此时路径黑节点数目不变
兄弟变红，然后父亲变黑
- 如果父亲是黑⚫️，说明这条路径还是少黑，再次让父节点触发双黑
- 将兄弟变为红色，那么以2为根的子树就黑色平衡了。
- 再把叔叔也变红色，此时以4为根的子树就平衡了。
- 再次递归，把12变红色，就平衡了。
case 5：被调整节点的兄弟为黑⚫️，至少一个红🔴侄子
- 如果兄弟是左孩子，左侄子是红🔴，LL 不平衡
- 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑⚫️，平衡起见，左侄子也是黑⚫️
- 原来兄弟要成为父亲，需要保留父亲颜色
示例2：
- 如果兄弟是左孩子，右侄子是红🔴，LR 不平衡
- 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑⚫️
- 右侄子会取代原来父亲，因此它保留父亲颜色
- 兄弟已经是黑了⚫️，无需改变
- 节点1左旋，变为LL
- 节点3右旋
- 如果兄弟是右孩子，右侄子是红🔴，RR 不平衡
- 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑⚫️，平衡起见，右侄子也是黑⚫️
- 原来兄弟要成为父亲，需要保留父亲颜色
- 如果兄弟是右孩子，左侄子是红🔴，RL 不平衡
- 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑⚫️
- 左侄子会取代原来父亲，因此它保留父亲颜色
- 兄弟已经是黑了⚫️，无需改变
fixDoubleBlack方法：
// 处理双黑 (case3、case4、case5)
private void fixDoubleBlack(Node x) {
if (x == root) {
return;
}
Node parent = x.parent;
Node sibling = x.sibling();
// case 3 兄弟节点是红色
if (isRed(sibling)) {
if (x.isLeftChild()) {
leftRotate(parent);
} else {
rightRotate(parent);
}
parent.color = Color.RED; // 父亲原来肯定是黑色，否则红红相邻
sibling.color = Color.BLACK;
fixDoubleBlack(x);
return;
}
if (sibling != null) {
// case 4 兄弟是黑色, 两个侄子也是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
sibling.color = Color.RED;
if (isRed(parent)) {
parent.color = Color.BLACK;
} else {
fixDoubleBlack(parent);
}
}
// case 5 兄弟是黑色, 侄子有红色
else {
// LL
if (sibling.isLeftChild() && isRed(sibling.left)) {
rightRotate(parent);
sibling.left.color = Color.BLACK;
sibling.color = parent.color;
}
// LR
else if (sibling.isLeftChild() && isRed(sibling.right)) {
sibling.right.color = parent.color;
leftRotate(sibling);
rightRotate(parent);
}
// RL
else if (!sibling.isLeftChild() && isRed(sibling.left)) {
sibling.left.color = parent.color;
rightRotate(sibling);
leftRotate(parent);
}
// RR
else {
leftRotate(parent);
sibling.right.color = Color.BLACK;
sibling.color = parent.color;
}
parent.color = Color.BLACK;
}
} else {
// @TODO 实际也不会出现，触发双黑后，兄弟节点不会为 null
fixDoubleBlack(parent);
}
}
doRemove方法：
private void doRemove(Node deleted) {
Node replaced = findReplaced(deleted);
Node parent = deleted.parent;
// 没有孩子
if (replaced == null) {
// case 1_1 删除的是根节点
if (deleted == root) {
root = null;
} else {
if (isBlack(deleted)) {
// 复杂调整
fixDoubleBlack(deleted);
} else {
// 红色叶子, 无需任何处理
}
if (deleted.isLeftChild()) {
parent.left = null;
} else {
parent.right = null;
}
deleted.parent = null;
}
return;
}
// 有一个孩子
if (deleted.left == null || deleted.right == null) {
// case 1_2 删除的是根节点
if (deleted == root) {
root.key = replaced.key;
root.value = replaced.value;
root.left = root.right = null;
} else {
if (deleted.isLeftChild()) {
parent.left = replaced;
} else {
parent.right = replaced;
}
replaced.parent = parent;
deleted.left = deleted.right = deleted.parent = null; // help 垃圾回收
// 删除节点和剩下节点都是黑
if (isBlack(deleted) && isBlack(replaced)) {
// 复杂处理 @TODO 实际不会有这种情况 因为只有一个孩子时 被删除节点是黑色 那么剩余节点只能是红色不会触发双黑
fixDoubleBlack(replaced);
} else {
// case 2 删除是黑，剩下是红
replaced.color = Color.BLACK;
}
}
return;
}
// case 0: 有两个孩子 => 有一个孩子 或 没有孩子
int t = deleted.key;
deleted.key = replaced.key;
replaced.key = t;
Object v = deleted.value;
deleted.value = replaced.value;
replaced.value = v;
doRemove(replaced);
}
4. 小结
| 维度 | 普通二叉搜索树 | AVL树 | 红黑树 |
|---|---|---|---|
| 查询 | 平均 O(logn) ，最坏 O(n) |
O(logn) |
O(logn) |
| 插入 | 平均 O(logn) ，最坏 O(n) |
O(logn) |
O(logn) |
| 删除 | 平均 O(logn) ，最坏 O(n) |
O(logn) |
O(logn) |
| 平衡性 | 不平衡 | 严格平衡 | 近似平衡 |
| 结构 | 二叉树 | 自平衡的二叉树 | 具有红黑性质的自平衡二叉树 |
| 查找效率 | 低 | 高 | 高 |
| 插入删除效率 | 低 | 中等 | 高 |
普通二叉搜索树插入、删除、查询的时间复杂度与树的高度相关，因此在最坏情况下，时间复杂度为 O(n)，而且容易退化成链表，查找效率低。
AVL树是一种高度平衡的二叉搜索树，其左右子树的高度差不超过1。因此，它能够在 logn 的平均时间内完成插入、删除、查询操作，但是在维护平衡的过程中，需要频繁地进行旋转操作，导致插入删除效率较低。
红黑树是一种近似平衡的二叉搜索树，它在保持高度平衡的同时，又能够保持较高的插入删除效率。红黑树通过节点着色和旋转操作来维护平衡。红黑树在维护平衡的过程中，能够进行较少的节点旋转操作，因此插入删除效率较高，并且查询效率也较高。
综上所述，红黑树具有较高的综合性能，是一种广泛应用的数据结构。
5. B树
5.1 概述
B树（B-Tree）结构是一种高效存储和查询数据的方法，B树结构非常适合应用于磁盘等大型存储器的高效操作，被广泛应用于关系数据库和文件系统中。
B树结构有很多变种和升级版，例如B+树，B*树和SB树等。这些变种和升级版本都基于B树的核心思想，通过调整B树的参数和结构，提高了B树在不同场景下的性能表现。
总的来说，B树结构是一个非常重要的数据结构，为高效存储和查询大量数据提供了可靠的方法。
- 100万的数据使用 avl 树来存储，树高是多少? 20
- 100万的数据，如果存储到B-树(最小度数是500)，那么树高大约是多少? 3
5.2 特性
度 degree：指树中节点孩子数
阶 order：指所有节点孩子数最大值
- 每个节点最多有
m个孩子，其中m称为B-树的阶 - 除根节点和叶子节点外，其他每个节点至少有
ceil(m/2)个孩子 - 若根节点不是叶子节点，则至少有两个孩子
- 所有叶子节点都在同一层
- 每个非叶子节点由
n个关键字和n+1个指针组成，其中（如上图节点6 8，key比value多1）：ceil(m/2)-1<=n<=m-1孩子（value）数：ceil(m/2)~m关键字（key）数：ceil(m/2)-1~m-1 - 关键字按升序排列，即节点中的第
i个关键字大于等于第i-1个关键字 - 指针
P[i]指向关键字值位于第i个关键字和第i+1个关键字之间的子树。
- 最小度数 t（节点的孩子数称为度）和节点中键数量的关系如下：每一个内部节点（非叶子节点）至少包含d-1个键值，至多包含2d-1个键值。
| 最小度数t | 键数量范围 |
|---|---|
| 2 | 1 ~ 3（如上图节点6 8，其最小度数为2） |
| 3 | 2 ~ 5 |
| 4 | 3 ~ 7 |
| ... | ... |
| n | (n-1) ~ (2n-1) |
其中，当节点中键数量达到其最大值时，即 3、5、7 ... 2n-1，需要分裂
问：
B-树为什么有最小度数的限制？
答：
B树中有最小度数的限制是为了保证B树的平衡特性。
在B树中，每个节点都可以有多个子节点，这使得B树可以存储大量的键值，但也带来了一些问题。如果节点的子节点数量太少，那么就可能导致B树的高度过高，从而降低了B树的效率。此外，如果节点的子节点数量太多，那么就可能导致节点的搜索、插入和删除操作变得复杂和低效。
最小度数的限制通过限制节点的子节点数量，来平衡这些问题。在B树中，每个节点的子节点数量都必须在一定的范围内，即
t到2t之间（其中t为最小度数）
5.3 节点类
static class Node {
boolean leaf = true;
int keyNumber;
int t;
int[] keys;
Node[] children;
public Node(int t) {
this.t = t;
this.keys = new int[2 * t - 1];
this.children = new Node[2 * t];
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOfRange(keys, 0, keyNumber));
}
}
leaf表示是否为叶子节点keyNumber为keys中有效key数目t为最小度数，它决定了节点中key的最小、最大数目，分别是t-1和2t-1keys存储此节点的keychildren存储此节点的childtoString只是为了方便调试和测试，非必须
实际
keys应当改为entries以便同时保存key和value，刚开始简化实现
多路查找：
为上面节点类添加 get 方法
Node get(int key) {
int i = 0;
while (i < keyNumber && keys[i] < key) {
i++;
}
if (i < keyNumber && keys[i] == key) {
return this;
}
if (leaf) {
return null;
}
return children[i].get(key); // 小于 key 的 child 刚好对应 i
}
插入 key 和 child ：
为上面节点类添加 insertKey 和 insertChild 方法
void insertKey(int key, int index) {
System.arraycopy(keys, index, keys, index + 1, keyNumber - index); // 向后移动一位
keys[index] = key; //
keyNumber++;
}
void insertChild(Node child, int index) {
System.arraycopy(children, index, children, index + 1, keyNumber - index);
children[index] = child;
}
作用是向 keys 数组或 children 数组指定 index 处插入新数据，插入时注意：
- 由于使用了静态数组，并且不会在新增或删除时改变它的大小，因此需要额外的
keyNumber来指定数组内有效key的数目- 插入时
keyNumber++ - 删除时减少
keyNumber的值即可
- 插入时
children不会单独维护数目，它比keys多一个- 如果这两个方法同时调用，注意它们的先后顺序，
insertChild后调用，因为它计算复制元素个数时用到了keyNumber
完整代码：
static class Node {
int[] keys; // 关键字
Node[] children; // 孩子
int keyNumber; // 有效关键字数目
boolean leaf = true; // 是否是叶子节点
int t; // 最小度数 (最小孩子数)
public Node(int t) { // t>=2
this.t = t;
this.children = new Node[2 * t];
this.keys = new int[2 * t - 1];
}
public Node(int[] keys) {
this.keys = keys;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOfRange(keys, 0, keyNumber));
}
// 多路查找
Node get(int key) {
int i = 0;
while (i < keyNumber) {
if (keys[i] == key) {
return this;
}
if (keys[i] > key) {
break;
}
i++;
}
// 执行到此时 keys[i]>key 或 i==keyNumber
if (leaf) {
return null;
}
// 非叶子情况，以上两种情况都适用
// 去第i个孩子里 继续找
return children[i].get(key);
}
// 向 keys 指定索引处插入 key
void insertKey(int key, int index) {
// 向后移动
System.arraycopy(keys, index, keys, index + 1, keyNumber - index);
keys[index] = key;
keyNumber++;
}
// 向 children 指定索引处插入 child
// [1,,3,5] -> [1,2,3,5]
void insertChild(Node child, int index) {
System.arraycopy(children, index, children, index + 1, keyNumber - index);
children[index] = child;
}
// 移除指定 index 处的 key
int removeKey(int index) {
int t = keys[index];
System.arraycopy(keys, index + 1, keys, index, --keyNumber - index);
return t;
}
// 移除最左边的 key
int removeLeftmostKey() {
return removeKey(0);
}
// 移除最右边的 key
int removeRightmostKey() {
return removeKey(keyNumber - 1);
}
// 移除指定 index 处的 child
Node removeChild(int index) {
Node t = children[index];
System.arraycopy(children, index + 1, children, index, keyNumber - index);
children[keyNumber] = null; // help GC
return t;
}
// 移除最左边的 child
Node removeLeftmostChild() {
return removeChild(0);
}
// 移除最右边的 child
Node removeRightmostChild() {
return removeChild(keyNumber);
}
// index 孩子处左边的兄弟
Node childLeftSibling(int index) {
return index > 0 ? children[index - 1] : null;
}
// index 孩子处右边的兄弟
Node childRightSibling(int index) {
return index == keyNumber ? null : children[index + 1];
}
// 复制当前节点的所有 key 和 child 到 target
void moveToTarget(Node target) {
int start = target.keyNumber;
if (!leaf) {
for (int i = 0; i <= keyNumber; i++) {
target.children[start + i] = children[i];
}
}
for (int i = 0; i < keyNumber; i++) {
target.keys[target.keyNumber++] = keys[i];
}
}
}
5.4 树定义
public class BTree {
Node root;
int t; // 树中节点最小度数
final int MIN_KEY_NUMBER; // 最小key数目
final int MAX_KEY_NUMBER; // 最大key数目
public BTree() {
this(2); // 默认最小值为2
}
public BTree(int t) {
this.t = t;
root = new Node(t);
MAX_KEY_NUMBER = 2 * t - 1;
MIN_KEY_NUMBER = t - 1;
}
}
5.5 树方法
contains:
// 1. 是否存在
public boolean contains(int key) {
return root.get(key) != null;
}
put插入：
// 2. 新增
public void put(int key) {
doPut(root, key, null, 0);
}
private void doPut(Node node, int key, Node parent, int index) {
int i = 0;
// 查找
while (i < node.keyNumber) {
if (node.keys[i] == key) {
return; // 更新
}
if (node.keys[i] > key) {
break; // 找到了插入位置，即为此时的 i
}
i++;
}
if (node.leaf) {
node.insertKey(key, i);
} else {
doPut(node.children[i], key, node, i);
}
// 需要分裂
if (node.keyNumber == MAX_KEY_NUMBER) {
split(node, parent, index);
}
}
- 首先查找本节点中的插入位置
i，如果没有空位（key被找到），应该走更新的逻辑，目前什么没做 - 接下来分两种情况
- 如果节点是叶子节点，可以直接插入了
- 如果节点是非叶子节点，需要继续在
children[i]处继续递归插入
- 无论哪种情况，插入完成后都可能超过节点
keys数目限制，此时应当执行节点分裂- 参数中的
parent和index都是给分裂方法用的，代表当前节点父节点，和分裂节点是第几个孩子
- 参数中的
判断依据为：
boolean isFull(Node node) {
return node.keyNumber == MAX_KEY_NUMBER;
}
spilt分裂：
split前：（t=2）
split后：（t=2）
分两种情况：
- 如果
parent == null表示要分裂的是根节点，此时需要创建新根，原来的根节点作为新根的 0 孩子 - 否则
- 创建
right节点（分裂后大于当前left节点的，移到右侧），把 t 以后的key和child都拷贝过去【如上图，索引 1 后的孩子称为新right】（中间点之后一小半，较大的） t-1处（中间处）的key插入到parent的 index 处，index指left作为孩子时的索引（parent的第几个孩子）【如上图，4在被移上去前，为父节点的索引1孩子，因此4上去后也将作为索引1处的key】right节点作为parent的孩子插入到index + 1处
- 创建
有孩子的情况：
分裂前：
分裂孩子：
分裂后：
完整代码：
/**
* <h3>分裂方法</h3>
*
* @param left 要分裂的节点
* @param parent 分裂节点的父节点
* @param index 分裂节点是第几个孩子
*/
void split(Node left, Node parent, int index) {
// 分裂的是根节点
if (parent == null) {
Node newRoot = new Node(t);
newRoot.leaf = false;
newRoot.insertChild(left, 0); // @TODO keyNumber 的维护（新节点没有孩子，应该不会有问题）
this.root = newRoot;
parent = newRoot;
}
// 1. 创建 right 节点，把 left 中 t 之后的 key 和 child 移动过去
Node right = new Node(t);
right.leaf = left.leaf; // 和分离前属性一样
// 把 t 及后面的元素 拷贝到 right新节点
System.arraycopy(left.keys, t, right.keys, 0, t - 1);
// 分裂节点是非叶子的情况
if (!left.leaf) {
// 拷贝孩子
System.arraycopy(left.children, t, right.children, 0, t); // 拷贝比节点多一个
// 删除原来 存在于left 的child
for (int i = t; i <= left.keyNumber; i++) {
left.children[i] = null;
}
}
// 修改左右有效keyNumber
right.keyNumber = t - 1;
left.keyNumber = t - 1;
// 2. 中间的 key （t-1 处）插入到父节点
int mid = left.keys[t - 1];
parent.insertKey(mid, index);
// 3. right 节点作为父节点的孩子
parent.insertChild(right, index + 1);
}
删除remove key：
case 1：当前节点是叶子节点，没找到
case 2：当前节点是叶子节点，找到了
case 3：当前节点是非叶子节点，没找到
case 4：当前节点是非叶子节点，找到了
case 5：删除后 key 数目 < 下限（不平衡）
case 6：根节点
是否找到key：
private boolean found(Node node, int key, int i) {
return i < node.keyNumber && node.keys[i] == key;
}
左右旋及合并：
例如删除key5后，右侧节点6不平衡：（t=3）
父节点4旋转下来，左节点3旋转上去：（右旋）
反之，如果左边不平衡，左旋。
加入remove后兄弟没有多余的节点：（t=3）
向左合并，舍弃右边节点：
如果上面删除的是左边，也是向左合并。
舍弃根节点，用0号孩子替换root
示例2：remove后两边都不够，有左兄弟：
合并后：
示例3：没有左兄弟，向自己合并：
移除右兄弟，合并后：
更多示例：基础算法-174-B树-remove-演示1.mp4 and 2
调整平衡balance：
private void balance(Node parent, Node x, int i) {
// case 6 根节点
if (x == root) {
// 根节点没有key 并且有孩子（root不会被设置为null）
if (root.keyNumber == 0 && root.children[0] != null) {
root = root.children[0];
}
return;
}
// 左右兄弟
Node left = parent.childLeftSibling(i);
Node right = parent.childRightSibling(i);
// case 5-1 左边富裕，右旋
if (left != null && left.keyNumber > MIN_KEY_NUMBER) {
// a) 父节点中前驱key旋转下来
x.insertKey(parent.keys[i - 1], 0);
if (!left.leaf) {
// b) left中最大的孩子换爹
x.insertChild(left.removeRightmostChild(), 0);
}
// c) left中最大的key旋转上去
parent.keys[i - 1] = left.removeRightmostKey();
return;
}
// case 5-2 右边富裕，左旋
if (right != null && right.keyNumber > MIN_KEY_NUMBER) {
// a) 父节点中【后继】key旋转下来
x.insertKey(parent.keys[i], x.keyNumber);
// b) right中最小的孩子换爹
if (!right.leaf) { // 孩子的左右侧，为keyNumber + 1
x.insertChild(right.removeLeftmostChild(), x.keyNumber + 1);
}
// c) right中最小的key旋转上去
parent.keys[i] = right.removeLeftmostKey();
return;
}
// case 5-3 两边都不够借，向左合并
if (left != null) {
// 向左兄弟合并
parent.removeChild(i); // parent删除被调整节点
left.insertKey(parent.removeKey(i - 1), left.keyNumber); // 父key移到左兄弟
x.moveToTarget(left); // 被调整节点所有key child移到左兄弟
} else {
// 向自己合并
parent.removeChild(i + 1);
x.insertKey(parent.removeKey(i), x.keyNumber);
right.moveToTarget(x); // 右兄弟向被调整节点合并
}
}
remove方法：
private void doRemove(Node parent, Node node, int index, int key) {
int i = 0;
while (i < node.keyNumber) {
if (node.keys[i] >= key) {
break;
}
i++;
}
// i 找到：代表待删除 key 的索引
// i 没找到： 代表到第i个孩子继续查找
if (node.leaf) {
if (!found(node, key, i)) { // case1
return;
} else { // case2
node.removeKey(i);
}
} else {
if (!found(node, key, i)) { // case3
doRemove(node, node.children[i], i, key); // 递归找孩子节点删除
} else { // case4
// 1. 找到后继 key
Node s = node.children[i + 1];
while (!s.leaf) {
s = s.children[0]; // 孩子走到头
}
int skey = s.keys[0]; // 拿最左侧的key
// 2. 替换待删除 key
node.keys[i] = skey;
// 3. 删除后继 key
doRemove(node, node.children[i + 1], i + 1, skey);
}
}
if (node.keyNumber < MIN_KEY_NUMBER) {
// 调整平衡 case 5 case 6
balance(parent, node, index);
}
}
6. 哈希表
6.1 概述
哈希表：
- 给每份数据分配一个编号，放入表格（数组）。
- 建立编号与表格索引的关系，将来就可以通过编号快速查找数据
- 理想情况编号当唯一，数组能容纳所有数据
- 现实是不能说为了容纳所有数据造一个超大数组，编号也有可能重复
解决：
- 有限长度的数组，以【拉链】方式存储数据
- 允许编号适当重复，通过数据自身来进行区分
6.2 节点类
// 节点类
static class Entry {
int hash; // 哈希码
Object key; // 键
Object value; // 值
Entry next;
public Entry(int hash, Object key, Object value) {
this.hash = hash;
this.key = key;
this.value = value;
}
}
6.3 代码
1.为什么计算索引位置用式子：
【hash & (数组长度-1)】 等价于 【hash % 数组长度】
10进制中去除以 10，100，1000时，余数就是【被除数】的后1，2，3 位
10^1 10^2 10^3
2进制中去除以 '10'，'100'，'1000' （二进制）时，余数也是【被除数】的后1，2，3 位
2^1 2^2 2^3
因此求余数就是求二进制的后几位，而保留二进制后几位可以通过与
1，3，7，11 ... 等数字按位与来实现，这些数字恰巧是数组长度-1
2.为什么旧链表会拆分成两条，一条 hash & 旧数组长度==0 另一条!=0
旧数组长度换算成二进制后，其中的 1 就是我们要检查的倒数第几位
旧数组长度 8 二进制 => 1000 （扩容后）检查倒数第4位（即与8进行按位与）
旧数组长度 16 二进制 => 10000 检查倒数第5位
hash & 旧数组长度 就是用来检查扩容前后索引位置（余数）会不会变
（4 的倍数 4 8 12 16 20 24 去除以 8 一半除得尽，一半除不尽）
3.为什么拆分后的两条链表，一个原索引不变，另一个是原索引+旧数组长度
倒数第n位是0的，索引不变，倒数后第n为变1，则相当于索引加了数组长度
扩容两倍后，索引又后三位变为后四位决定，倒数第四位为0则没有影响，为1则导致索引变化。
它们都有个共同的前提：数组长度是 2 的 n 次方
代码：
import com.google.common.collect.Table;
import com.google.common.hash.Hashing;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
/**
* <h2>哈希表</h2>
*/
public class HashTable {
// 摘要算法
// 散列算法
// 节点类
static class Entry {
int hash; // 哈希码
Object key; // 键
Object value; // 值
Entry next;
public Entry(int hash, Object key, Object value) {
this.hash = hash;
this.key = key;
this.value = value;
}
}
Entry[] table = new Entry[16];
int size = 0; // 元素个数
float loadFactor = 0.75f; // 12 阈值
int threshold = (int) (loadFactor * table.length);
/* 求模运算替换为位运算
- 前提：数组长度是 2 的 n 次方
- hash % 数组长度 等价于 hash & (数组长度-1)
*/
// 根据 hash 码获取 value
Object get(int hash, Object key) {
int idx = hash & (table.length - 1);
if (table[idx] == null) {
return null;
}
Entry p = table[idx];
while (p != null) {
if (p.key.equals(key)) {
return p.value;
}
p = p.next;
}
return null;
}
// 向 hash 表存入新 key value，如果 key 重复，则更新 value
void put(int hash, Object key, Object value) {
int idx = hash & (table.length - 1);
if (table[idx] == null) {
// 1. idx 处有空位, 直接新增
table[idx] = new Entry(hash, key, value);
} else {
// 2. idx 处无空位, 沿链表查找 有重复key更新，否则新增
Entry p = table[idx];
while (true) {
if (p.key.equals(key)) {
p.value = value; // 更新
return; // size不++
}
if (p.next == null) { // 找到空位 退出
break;
}
p = p.next;
}
p.next = new Entry(hash, key, value); // 新增
}
size++;
if (size > threshold) {
resize();
}
}
private void resize() {
Entry[] newTable = new Entry[table.length << 1];
for (int i = 0; i < table.length; i++) {
Entry p = table[i]; // 拿到每个链表头
if (p != null) {
/*
拆分链表，移动到新数组，拆分规律
* 一个链表最多拆成两个
* hash & table.length == 0 的一组
* hash & table.length != 0 的一组
p
0->8->16->24->32->40->48->null
a
0->16->32->48->null
b
8->24->40->null
*/
Entry a = null;
Entry b = null;
Entry aHead = null;
Entry bHead = null;
while (p != null) {
if ((p.hash & table.length) == 0) {
if (a != null) {
a.next = p;
} else {
aHead = p;
}
a = p; // 分配到a
} else {
if (b != null) {
b.next = p;
} else {
bHead = p;
}
b = p; // 分配到b
}
p = p.next;
}
// 规律： a 链表保持索引位置不变，b 链表索引位置+table.length
if (a != null) {
a.next = null;
newTable[i] = aHead;
}
if (b != null) {
b.next = null;
newTable[i + table.length] = bHead;
}
}
}
table = newTable;
threshold = (int) (loadFactor * table.length);
}
// 根据 hash 码删除，返回删除的 value
Object remove(int hash, Object key) {
int idx = hash & (table.length - 1);
if (table[idx] == null) {
return null;
}
Entry p = table[idx];
Entry prev = null;
while (p != null) {
if (p.key.equals(key)) {
// 找到了, 删除
if (prev == null) { // 链表头
table[idx] = p.next;
} else { // 非链表头
prev.next = p.next;
}
size--;
return p.value;
}
prev = p;
p = p.next;
}
return null;
}
public static void main(String[] args) throws IOException {
HashTable table = new HashTable();
/*for (int i = 0; i < 200000; i++) {
Object obj = new Object();
table.put(obj, obj);
}*/
/*List<String> strings = Files.readAllLines(Path.of("words"));
for (String string : strings) {
table.put(string, string);
}*/
table.put(2, 2);
table.put(524290, 2);
table.print();
}
}
6.4 生成hash码
hash 算法是将任意对象，分配一个编号的过程，其中编号是一个有限范围内的数字（如 int 范围内）
Object.hashCode
Object的hashCode方法默认是生成随机数作为 hash 值（int类型）（会缓存在对象头当中）- 缺点是包含相同值的不同对象，他们的
hashCode不一样，不能够用hash值来反映对象的值特征，因此诸多子类都会重写hashCode方法
String.hashCode
public static void main(String[] args) {
String s1 = "bac";
String s2 = new String("abc");
System.out.println(s1.hashCode()); // 96354
System.out.println(s2.hashCode()); // 96354
// 原则：值相同的字符串生成相同的 hash 码, 尽量让值不同的字符串生成不同的 hash 码
/*
对于 abc a * 100 + b * 10 + c
对于 bac b * 100 + a * 10 + c
*/
int hash = 0;
for (int i = 0; i < s1.length(); i++) {
char c = s1.charAt(i);
System.out.println((int) c);
// (a*10 + b)*10 + c ==> a*100 + b*10 + c 2^5
hash = (hash << 5) - hash + c;
}
System.out.println(hash);
}
- 经验表明如果每次乘的是较大质数，可以有更好地降低 hash 冲突，因此改【乘 10】为【乘 31】
- 【乘 31】可以等价为【乘 32 - hash】，进一步可以转为更高效地【左移5位 - hash】
检查 hash 表的分散性：
// 检查 hash 表的分散性
public void print() {
int[] sums = new int[table.length];
for (int i = 0; i < table.length; i++) {
Entry p = table[i];
while (p != null) {
sums[i]++;
p = p.next;
}
}
// System.out.println(Arrays.toString(sums));
// 根据结果 个数 分组
Map<Integer, Long> collect = Arrays.stream(sums).boxed().collect(Collectors.groupingBy(e -> e, Collectors.counting()));
System.out.println(collect);
}
public static void main(String[] args) throws IOException {
HashTable table = new HashTable();
for (int i = 0; i < 200000; i++) {
Object obj = new Object();
table.put(obj, obj);
}
// 字符串读取
/*List<String> strings = Files.readAllLines(Path.of("words"));
for (String string : strings) {
table.put(string, string);
}*/
// 冲突：
// table.put(2, 2);
// table.put(524290, 2);
table.print();
}
MurmurHash
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>30.1.1-jre</version>
</dependency>
示例：
int abc = Hashing.murmur3_32().hashString("abc", StandardCharsets.UTF_8).asInt();
System.out.println(abc); // -1277324294
更新后代码：
public Object get(Object key) {
int hash = hash(key);
return get(hash, key);
}
public void put(Object key, Object value) {
int hash = hash(key);
put(hash, key, value);
}
public Object remove(Object key) {
int hash = hash(key);
return remove(hash, key);
}
private static int hash(Object key) {
if (key instanceof String k) { // 字符串类型
return Hashing.murmur3_32().hashString(k, StandardCharsets.UTF_8).asInt();
}
int hash = key.hashCode();
// 减少哈希冲突
return hash ^ (hash >>> 16);
}
6.5 小结
- 我们的代码里使用了尾插法，如果改成头插法呢？（多线程头插法死循环问题）
- JDK 的
HashMap中采用了将对象hashCode高低位相互异或的方式减少冲突，怎么理解？（综合高位及低位的值）static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } - 我们的
HashTable中表格容量是 2 的 n 次方，很多优化都是基于这个前提，能否不用 2 的 n 次方作为表格容量？（可以）基于该前提的优化： 1. 按位与 2. 拆分链表 3. 高低位异或 // ========== JDK自带的Hashtable public Hashtable() { this(11, 0.75f); } 初始容量：11 【质数】 分散性好 - JDK 的
HashMap在链表长度过长会转换成红黑树，对此你怎么看
（抗攻击数据，防范于未然）
6.6 例题
6.6.1 两数之和
给定一个整数数组
nums和一个整数目标值target，请你在该数组中找出 和为目标值target的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
示例：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
输入：nums = [3,2,4], target = 6
输出：[1,2]
输入：nums = [3,3], target = 6
输出：[0,1]
方法一：暴力枚举，双层 for 循环
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
}
方法二：哈希表：
注意到方法一的时间复杂度较高的原因是寻找
target - x的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。使用哈希表，可以将寻找
target - x的时间复杂度降低到从O(N)降低到O(1)。这样我们创建一个哈希表，对于每一个
x，我们首先查询哈希表中是否存在target - x，然后将x插入到哈希表中，即可保证不会让x和自己匹配。
class Solution {
public int[] twoSum(int[] nums, int target) {
// key 为 数据，value 为 索引
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
// map中是否已经包含 能和当前数据匹配的 数据，有则get并返回其value（索引）
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
// 没有则插入当前数据及其索引，为后面使用
hashtable.put(nums[i], i);
}
return new int[0];
}
}
6.6.2 无重复字符的最长子串
给定一个字符串
s，请你找出其中不含有重复字符的 最长子串 的长度。
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
方法一二：
要点：
（1）用 begin 和 end 表示子串开始和结束位置
（2）用 hash 表检查重复字符
（3）从左向右查看每个字符, 如果：
- 没遇到重复字符，调整
end - 遇到重复的字符，调整
begin - 将当前字符放入
hash表
（4）end - begin + 1 是当前子串长度
begin 调整时的解释，遇到重复的 begin 应该向右调整，例如
abca
- 遇到重复的
a，这时begin应该调整到上个重复字符a索引加 1 处，即map.get('a') + 1 = 1，
但还有一种情况需要考虑，就是连续遇到两次重复，例如
abba
- 遇到重复的
b，这时begin应该调整到上个重复字符b索引加1处，即map.get('b') + 1 = 2 - 不过接下来，又遇到了重复的 a，此时若还执行
map.get('a') + 1 = 1，则begin相当于向左退了，不对 - 应该是
Math.max(2, map.get('a') + 1)，即begin应该是两个重复字符索引中更靠右者
题目中说明 s 由英文字母、数字、符号和空格组成，因此它的范围是有限的（在 0 ~127 之内），可以用数组来替代 HashMap 优化，如下：
/**
* 无重复字符的最长子串
* <p>1. 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。</p>
* <p>2. s 由英文字母、数字、符号和空格组成</p>
*/
public class E02Leetcode3 {
/*
保留索引最新位置
[(a,3) (b,1) (c,2)]
b(begin)
e(end)
abcabcb
abcabcbb 3
a
ab
abc
bca (重复，移除原来第一个）
cab
abc
cb(向后找到不重复的，从原来第一个b后开始）
b
pwwkew 3
p
pw
w
wk
wke
kew
*/
public int lengthOfLongestSubstring(String s) {
/*
// 方法一：
HashMap<Character, Integer> map = new HashMap<>();
int begin = 0;
int maxLength = 0;
for(int end = 0; end < s.length(); end++) {
char ch = s.charAt(end);
if (map.containsKey(ch)) { // 重复
begin = Math.max(begin, map.get(ch) + 1);
// 下面行 存在漏洞：abba 碰到最后一个a, begin回头走了
// begin = map.get(ch) + 1; // 修改begin，在原来第一个索引处+1
map.put(ch, end);
} else {
map.put(ch, end); // 放入hash表
}
// System.out.println(s.substring(begin, end + 1)); // 输出拆分的子串
maxLength = Math.max(maxLength, end - begin + 1); // 更新最大子串长度
}
return maxLength;
*/
// 题目范围在 128 ascii内
// 使用数组
int[] map = new int[128];
Arrays.fill(map, -1);
int begin = 0;
int maxLength = 0;
for (int end = 0; end < s.length(); end++) {
char ch = s.charAt(end);
if (map[ch] != -1) { // 重复时调整 begin
begin = Math.max(begin, map[ch] + 1);
map[ch] = end;
} else { // 不重复
map[ch] = end;
}
// System.out.println(s.substring(begin, end + 1));
maxLength = Math.max(maxLength, end - begin + 1);
}
return maxLength;
}
public static void main(String[] args) {
E02Leetcode3 e02 = new E02Leetcode3();
/* 拆分结果如下：
* a
* ab
* abc
* bca
* cab
* abc
* cb
* b
*/
System.out.println(e02.lengthOfLongestSubstring("abcabcbb")); // 3
/*
[(a,0),(b,2)]
b
e
abba
*/
System.out.println(e02.lengthOfLongestSubstring("abba")); // 2
// System.out.println(e02.lengthOfLongestSubstring("abca"));
}
}
力扣题解：滑动窗口
思路和算法：
我们先用一个例子考虑如何在较优的时间复杂度内通过本题。
我们不妨以示例一中的字符串
abcabcbb为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb 以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb 以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb 以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb 以 abca(b)cbb 开始的最长字符串为 abca(bc)bb 以 abcab(c)bb 开始的最长字符串为 abcab(cb)b 以 abcabc(b)b 开始的最长字符串为 abcabc(b)b 以 abcabcb(b) 开始的最长字符串为 abcabcb(b)发现了什么？如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！这里的原因在于，假设我们选择字符串中的第
k个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为r_k。那么当我们选择第k+1个字符作为起始位置时，首先从k+1到r_k的字符显然是不重复的，并且由于少了原本的第k个字符，我们可以尝试继续增大r_k，直到右侧出现了重复字符为止。这样一来，我们就可以使用「滑动窗口」来解决这个问题了：
- 我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为上文中的
r_k；- 在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；
- 在枚举结束后，我们找到的最长的子串的长度即为答案。
判断重复字符
在上面的流程中，我们还需要使用一种数据结构来判断 是否有重复的字符，常用的数据结构为哈希集合（Java 中的
HashSet）。在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合中添加一个字符。至此，我们就完美解决了本题。(leetcode官方代码比较费神，精选题解代码与上面基本一样，故省略)，以下为精选题解的高赞评论代码（解释）：
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap<>();
int maxLen = 0;//用于记录最大不重复子串的长度
int left = 0;//滑动窗口左指针
for (int i = 0; i < s.length() ; i++)
{
/**
1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,
此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；
2、如果当前字符 ch 包含在 map中，此时有2类情况：
1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，
那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；
2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，
而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；
随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时
应该不变，left始终为2，子段变成 ba才对。
为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).
另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，
因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！
*/
if(map.containsKey(s.charAt(i)))
{
left = Math.max(left , map.get(s.charAt(i))+1);
}
//不管是否更新left，都要更新 s.charAt(i) 的位置！
map.put(s.charAt(i) , i);
maxLen = Math.max(maxLen , i-left+1);
}
return maxLen;
}
复杂度分析：
- 时间复杂度：
O(N)，其中N是字符串的长度。左指针和右指针分别会遍历整个字符串一次。 - 空间复杂度：
O(∣Σ∣)，其中Σ表示字符集（即字符串中可以出现的字符），∣Σ∣表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在[0,128)内的字符，即∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有∣Σ∣个，因此空间复杂度为O(∣Σ∣)。
6.6.3 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。(字母相同，顺序不同)
strs[i]仅包含小写字母
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
输入: strs = [""]
输出: [[""]]
输入: strs = ["a"]
输出: [["a"]]
解法一：
把每个词转为
charArray，再排序，排序后拼成字符串插入得到hashmap中。往后遍历后如hashmap有该字母序列则插入链表。
// 排序前 排序后
// eat tea ate => aet
// tan nat => ant
// bat => abt
// key value ↓
// [(aet,{eat,tea}), (ant,{tan})]
/*
解法1 思路
1. 遍历字符串数组，每个字符串中的字符重新排序后作为 key
2. 所谓分组，其实就是准备一个集合，把这些单词加入到 key 相同的集合中
3. 返回分组结果
*/
public List<List<String>> groupAnagrams1(String[] strs) { // 6ms
HashMap<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars); // 重排序
String key = new String(chars); // 排序后的字符串
/*List<String> list = map.get(key);
if (list == null) {
list = new ArrayList<>();
map.put(key, list);
}
list.add(str);*/
// 如果key不存在，则创建空的ArrayList。否则不执行
List<String> list = map.computeIfAbsent(key, k -> new ArrayList<>());
list.add(str);
}
return new ArrayList<>(map.values());
}
解法2：
/*
题目中有说明：strs[i] 仅包含小写字母
26个字符，出现一次对应的索引 +1
key = [2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0] 26
key = [2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0] 26
"eaat", "teaa"
*/
// 封装 基于Array数组进行key的hashCode比较
static class ArrayKey {
int[] key = new int[26];
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
ArrayKey arrayKey = (ArrayKey) o;
return Arrays.equals(key, arrayKey.key);
}
@Override
public int hashCode() {
return Arrays.hashCode(key);
}
// 将字符 映射 到 索引
public ArrayKey(String str) {
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i); // 'a':97-97=0 'b':98-97 'a'
key[ch - 97]++;
}
}
}
public List<List<String>> groupAnagrams(String[] strs) { // 5ms
HashMap<ArrayKey, List<String>> map = new HashMap<>();
for (String str : strs) {
ArrayKey key = new ArrayKey(str);
List<String> list = map.computeIfAbsent(key, k -> new ArrayList<>());
list.add(str);
}
return new ArrayList<>(map.values());
}
6.6.4 存在重复元素
217. 存在重复元素 【简单】
给你一个整数数组
nums。如果任一值在数组中出现 至少两次 ，返回true；如果数组中每个元素互不相同，返回false。输入：nums = [1,2,3,1] 输出：true 输入：nums = [1,2,3,4] 输出：false
使用
HashSet，如果set.add(key)返回false则表示已存在，即可返回true。（效率比用set.contains(key)高）
public boolean containsDuplicate(int[] nums) { // 5ms
HashSet<Integer> set = new HashSet<>();
for (int key : nums) {
// 不存在则添加成功返回true，已存在则返回false
if (!set.add(key)) {
return true;
}
}
return false;
}
HashSet底层也是HashMap：
// HashSet
private transient HashMap<E,Object> map;
public boolean add(E e) {
// map的put方法，返回值为原来的【旧值】
return map.put(e, PRESENT)==null;
}
使用
map的返回值进行判断，必将value设置为固定值，将初始HashMap容量设置为数组两倍避免扩容。优化后代码：
public boolean containsDuplicate(int[] nums) {
// HashMap<Integer, Integer> map = new HashMap<>();
HashMap<Integer, Object> map = new HashMap<>(nums.length * 2); // 避免扩容
// value为固定对象
Object value = new Object();
for (int num : nums) {
Object put = map.put(num, value);
// 返回的旧值不为null，说明之前添加过
if (put != null) {
return true;
}
}
return false;
}
6.6.5 只出现一次的数字
给你一个 非空 整数数组
nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
输入：nums = [2,2,1]
输出：1
输入：nums = [4,1,2,1,2]
输出：4
输入：nums = [1]
输出：1
方法一：
使用
HashSet，因为题目表示除了要返回的元素，其他所有元素均出现两次，因此可以一次add，一次remove。剩下的就是想要的
public int singleNumber(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
if (!set.add(num)) {
set.remove(num);
}
}
// 转为Integer
return set.toArray(new Integer[0])[0];
}
方法二：
如何才能做到线性时间复杂度和常数空间复杂度呢？
答案是使用位运算（xor）。对于这道题，可使用异或运算 ⊕。异或运算有以下三个性质。
- 任何数和
0做异或运算，结果仍然是原来的数，即a⊕0=a。
- 任何数和其自身做异或运算，结果是
0，即a⊕a=0。
- 异或运算满足交换律和结合律，即
a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b
因此，数组中的全部元素的异或运算结果即为数组中只出现一次的数字。
class Solution {
public int singleNumber(int[] nums) {
int single = 0;
for (int num : nums) {
single ^= num;
}
return single;
}
}
- 时间复杂度：
O(n)，其中n是数组长度。只需要对数组遍历一次。- 空间复杂度：
O(1)。
6.6.6 有效的字母异位词
242. 有效的字母异位词 【简单】
给定两个字符串
s和t，编写一个函数来判断t是否是s的字母异位词。注意：若
s和t中每个字符出现的次数都相同，则称s和t互为字母异位词。
s和t仅包含小写字母进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
输入: s = "anagram", t = "nagaram"
输出: true
输入: s = "rat", t = "car"
输出: false
方法一：
个人思路：采用6.6.3的解法2，将出现的字符次数写入数组包装为
ArrayKey包装类，返回比较包装类结果。【3ms_41.1MB】
// 包装类代码忽略...
public boolean isAnagram(String s, String t) {
ArrayKey sKey = new ArrayKey(s);
ArrayKey tKey = new ArrayKey(t);
return sKey.equals(tKey);
}
方法二：
Arrays.equals(int[] a, int[] a2)【1ms_42.3MB】
public boolean isAnagram(String s, String t) { // 1ms
return Arrays.equals(getKey(s), getKey(t));
}
private static int[] getKey(String s) {
int[] array = new int[26];
char[] chars = s.toCharArray();
for (char ch : chars) {
array[ch - 'a']++;
}
return array;
}
- 其中用
s.toCharArray()性能明显高于用s.charAt()一个个获取字符
方法三：力扣题解 之 排序
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1, str2);
}
}
方法四：力扣题解 之 哈希表
t是s的异位词等价于「两个字符串中字符出现的种类和次数均相等」。由于字符串只包含26个小写字母，因此我们可以维护一个长度为
26的频次数组table，先遍历记录字符串s中字符出现的频次，然后遍历字符串t，减去table中对应的频次，如果出现table[i] < 0，则说明t包含一个不在s中的额外字符，返回false即可。
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] table = new int[26];
for (int i = 0; i < s.length(); i++) {
table[s.charAt(i) - 'a']++;
}
for (int i = 0; i < t.length(); i++) {
table[t.charAt(i) - 'a']--;
if (table[t.charAt(i) - 'a'] < 0) {
return false;
}
}
return true;
}
}
进阶问题的核心点在于「字符是离散未知的」，因此我们用哈希表维护对应字符的频次即可。同时读者需要注意 Unicode 一个字符可能对应多个字节的问题，不同语言对于字符串读取处理的方式是不同的。
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
Map<Character, Integer> table = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
table.put(ch, table.getOrDefault(ch, 0) + 1);
}
for (int i = 0; i < t.length(); i++) {
char ch = t.charAt(i);
table.put(ch, table.getOrDefault(ch, 0) - 1);
if (table.get(ch) < 0) {
return false;
}
}
return true;
}
}
6.6.7 第一个不重复字符
给定一个字符串
s，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回-1。
s只包含小写字母
输入: s = "leetcode"
输出: 0
输入: s = "loveleetcode"
输出: 2
输入: s = "aabb"
输出: -1
方法一：数组存储次数
两个
for循环，第一次统计字符，将次数加入数组。第二次遍历查看每个字符出现的次数，放回第一个次数等于1的。【3ms_43MB】
public int firstUniqChar(String s) {
int[] array = new int[26];
char[] chars = s.toCharArray();
// 添加次数
for (char ch : chars) {
array[ch-97]++;
}
// 获得次数并判断
for (int i = 0; i < chars.length; i++) {
char ch = chars[i];
if (array[ch - 97] == 1) {
return i;
}
}
return -1;
}
方法二：哈希表存储次数
力扣官方题解，方法一。【26ms_42.4MB】
在第一次遍历时，我们使用哈希映射统计出字符串中每个字符出现的次数。在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回它的索引，否则在遍历结束后返回
-1。
class Solution {
public int firstUniqChar(String s) {
Map<Character, Integer> frequency = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); ++i) {
char ch = s.charAt(i);
frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
}
for (int i = 0; i < s.length(); ++i) {
if (frequency.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
}
方法三：哈希表存储索引
我们可以对上面方法进行修改，使得第二次遍历的对象从字符串变为哈希映射。
具体地，对于哈希映射中的每一个键值对，键表示一个字符，值表示它的首次出现的索引（如果该字符只出现一次）或者
-1（如果该字符出现多次）。当我们第一次遍历字符串时，设当前遍历到的字符为c，如果c不在哈希映射中，我们就将c与它的索引作为一个键值对加入哈希映射中，否则我们将c在哈希映射中对应的值修改为-1。在第一次遍历结束后，我们只需要再遍历一次哈希映射中的所有值，找出其中不为
-1的最小值，即为第一个不重复字符的索引。如果哈希映射中的所有值均为-1，我们就返回-1。【20ms_43.1MB】
class Solution {
public int firstUniqChar(String s) {
Map<Character, Integer> position = new HashMap<Character, Integer>();
int n = s.length();
for (int i = 0; i < n; ++i) {
char ch = s.charAt(i);
if (position.containsKey(ch)) {
position.put(ch, -1);
} else {
position.put(ch, i);
}
}
int first = n;
for (Map.Entry<Character, Integer> entry : position.entrySet()) {
int pos = entry.getValue();
if (pos != -1 && pos < first) {
first = pos;
}
}
if (first == n) {
first = -1;
}
return first;
}
}
6.6.8 出现次数最多的单词
给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词。
题目保证至少有一个词不在禁用列表中，而且答案唯一。
禁用列表中的单词用小写字母表示，不含标点符号。段落中的单词不区分大小写。答案都是小写字母。
paragraph只包含字母、空格和下列标点符号!?',;.
输入:
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
输出: "ball"
解释:
"hit" 出现了3次，但它是一个禁用的单词。
"ball" 出现了2次 (同时没有其他单词出现2次)，所以它是段落里出现次数最多的，且不在禁用列表中的单词。
注意，所有这些单词在段落里不区分大小写，标点符号需要忽略（即使是紧挨着单词也忽略， 比如 "ball,"），
"hit"不是最终的答案，虽然它出现次数更多，但它在禁用单词列表中。
方法一：
先分组，再加入
hashmap，如果出现在禁用词set则不加入。使用较多lambda表达式。【12ms_40.6MB】
/*
1. 将 paragraph 截取为一个个单词
2. 将单词加入 map 集合，单词本身作为 key，出现次数作为 value，避免禁用词加入
3. 在 map 集合中找到 value 最大的，返回它对应的 key 即可
*/
public String mostCommonWord1(String paragraph, String[] banned) { // 14ms
// 转小写 // 除了字母以为都可能是分隔符
String[] split = paragraph.toLowerCase().split("[^A-Za-z]+");
// 禁词数组转set
Set<String> set = Set.of(banned);
// key 字符串 value 出现次数
HashMap<String, Integer> map = new HashMap<>();
for (String key : split) {
if (!set.contains(key)) { // 不包含在禁用词则可计算次数
map.compute(key, (k, v) -> v == null ? 1 : v + 1);
}
}
// Lambda方法返回 String
// Optional<Map.Entry<String, Integer>> optional = map.entrySet().stream().max(Map.Entry.comparingByValue());
// return optional.map(Map.Entry::getKey).orElse(null);
// for 循环 获取最大次数
int max = 0;
String maxKey = null;
for (Map.Entry<String, Integer> e : map.entrySet()) {
Integer value = e.getValue();
if (value > max) {
max = value;
maxKey = e.getKey();
}
}
return maxKey;
}
改进点一：lambda转for循环，如上
改进点二：正则表达式改为StringBuilder
修改后代码：【5ms_40.1MB】
public String mostCommonWord(String paragraph, String[] banned) { // 4ms
// bob hit a ball, ...
// 遇到a-z的字符，拼接，创建新的sb对象继续拼接
// bob
Set<String> set = Set.of(banned);
HashMap<String, Integer> map = new HashMap<>();
char[] chars = paragraph.toLowerCase().toCharArray();
StringBuilder sb = new StringBuilder();
for (char ch : chars) {
if (ch >= 'a' && ch <= 'z') {
sb.append(ch);
} else {
// 遇到分隔字符，且sb内有字符，判断，插入map
if(!sb.isEmpty()) {
String key = sb.toString();
if (!set.contains(key)) {
map.compute(key, (k, v) -> v == null ? 1 : v + 1);
}
// sb = new StringBuilder();
sb.setLength(0);
}
}
}
// 假如paragraph只有一个词，没有分隔字符，不会走到上面的else，需要最后再次判断
if (!sb.isEmpty()) {
String key = sb.toString();
if (!set.contains(key)) {
map.compute(key, (k, v) -> v == null ? 1 : v + 1);
}
}
// System.out.println(map);
int max = 0;
String maxKey = null;
for (Map.Entry<String, Integer> e : map.entrySet()) {
Integer value = e.getValue();
if (value > max) {
max = value;
maxKey = e.getKey();
}
}
return maxKey;
}
三、基于比较的排序算法
0. 对比
| 算法 | 最好 | 最坏 | 平均 | 空间 | 稳定 | 思想 | 注意事项 |
|---|---|---|---|---|---|---|---|
| 冒泡 | O(n) | O(n^2) |
O(n^2) |
O(1) | Y | 比较 | 最好情况需要额外判断 |
| 选择 | O(n^2) |
O(n^2) |
O(n^2) |
O(1) | N | 比较 | 交换次数一般少于冒泡 |
| 堆 | O(nlogn) |
O(nlogn) |
O(nlogn) |
O(1) | N | 选择 | 堆排序的辅助性较强，理解前先理解堆的数据结构 |
| 插入 | O(n) | O(n^2) |
O(n^2) |
O(1) | Y | 比较 | 插入排序对于近乎有序的数据处理速度比较快，复杂度有所下降，可以提前结束 |
| 希尔 | O(nlogn) |
O(n^2) |
O(nlogn) |
O(1) | N | 插入 | gap序列的构造有多种方式，不同方式处理的数据复杂度可能不同 |
| 归并 | O(nlogn) |
O(nlogn) |
O(nlogn) |
O(n) | Y | 分治 | 需要额外的 O(n) 的存储空间 |
| 快速 | O(nlogn) |
O(n^2) |
O(nlogn) |
O(logn) |
N | 分治 | 快排可能存在最坏情况，需要把枢轴值选取得尽量随机化来缓解最坏情况下的时间复杂度 |
稳定 vs 不稳定：
1. 冒泡排序
【见笔记001——5.3冒泡排序（递归版）】
冒泡排序，相邻元素比较，大的靠右，每一回合最大的元素沉底。
array.length-1轮后完成排序。思路：将数组分为已排序部分（右边）和未排序部分（左边），每回合已排序部分数量+1，即未排序部分索引-1。
优化：发生交换，意味着有无序情况。使用
变量x记录每回合最后一次交换的索引，意味这索引后面的元素是有序的，不需要再交换，下次遍历到索引x即可。
以数组 3、2、1 的冒泡排序为例，第一轮冒泡
第二轮冒泡
未排序区域内就剩一个元素，结束
优化手段：每次循环时，若能确定更合适的右边界，则可以减少冒泡轮数
以数组 3、2、1、4、5 为例，第一轮结束后记录的 x，即为右边界
非递归版代码
public class BubbleSort {
private static void bubble(int[] a) {
int j = a.length - 1; // 初始右边界
do {
int x = 0;
for (int i = 0; i < j; i++) {
if (a[i] > a[i + 1]) {
int t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
x = i; // 记录最后交换索引
}
}
j = x; // // 更新右边界
} while (j != 0);
}
public static void main(String[] args) {
int[] a = {6, 5, 4, 3, 2, 1};
System.out.println(Arrays.toString(a));
bubble(a);
System.out.println(Arrays.toString(a));
}
}
2. 选择排序
要点
- 每一轮选择，找出最大（最小）的元素，并把它交换到合适的位置
以下面的数组选择最大值为例
非递归实现：
/**
* <h3>选择排序</h3>
*/
public class SelectionSort {
public static void sort(int[] a) {
// 1. 选择轮数 a.length - 1
// 2. 交换后最大值到达的索引位置(right) 初始 a.length - 1, 每次递减
for (int right = a.length - 1; right > 0 ; right--) {
int max = right; // 记录最值索引
for (int i = 0; i < right; i++) {
if (a[i] > a[max]) {
max = i;
}
}
// 交换
if(max != right) {
int t = a[max];
a[max] = a[right];
a[right] = t;
}
}
}
public static void main(String[] args) {
int[] a = {6, 5, 4, 3, 2, 1};
System.out.println(Arrays.toString(a));
sort(a);
System.out.println(Arrays.toString(a));
}
}
自写递归算法：
/**
*
* @param a 需要排序的数组
* @param right 尚未有序的 右边界索引
*/
public static void sort(int[] a, int right) {
if (right == 0) {
return;
}
int max = right;
for (int i = 0; i < right; i++) {
if (a[i] > a[max]) {
max = i;
}
}
if (max != right) {
int t = a[max];
a[max] = a[right];
a[right] = t;
}
sort(a, right - 1);
}
3. 堆排序
见笔记002，【6.堆及6.3.1 堆排序例题】
要点：
- 建立大顶堆
heapify - 每次将堆顶元素（最大值）交换到末尾，堆缩小1，调整堆顶元素，让它重新符合大顶堆特性
- 重复第二步直至堆里剩一个元素
建堆
交换，下潜调整
堆顶（最大值）6交换到末尾，对交换上来的2进行下潜：
代码
/**
* <h3>堆排序</h3>
*/
public class HeapSort {
public static void sort(int[] a) {
heapify(a, a.length);
// 大顶堆，交换后down下潜调整后，索引0位置是最大值
for (int right = a.length - 1; right > 0; right--) {
swap(a, 0, right);
down(a, 0, right); // 第3个参数 是 size, 这里用索引，已经小了1
}
}
// 建堆 O(n)
private static void heapify(int[] array, int size) {
// 从非叶子节点开始，不停下潜
for (int i = size / 2 - 1; i >= 0; i--) {
down(array, i, size);
}
}
// 下潜
// leetcode 上数组排序题目用堆排序求解，非递归实现比递归实现大约快 6ms
private static void down(int[] array, int parent, int size) {
while (true) {
int left = parent * 2 + 1;
int right = left + 1;
int max = parent;
if (left < size && array[left] > array[max]) {
max = left;
}
if (right < size && array[right] > array[max]) {
max = right;
}
/* // 递归版 去掉上面的 while
if(max != parent) {
swap(array, max, parent);
down(array, max, size);
}*/
// ==== ↓ 非递归版 ↓ ====
if (max == parent) { // 没找到更大的孩子
break;
}
swap(array, max, parent);
parent = max; // 继续向下比较，被换下去的（原父节点）会不会小于孙子节点
// ==== ↑ 非递归版 ↑ ====
}
}
// 交换
private static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
public static void main(String[] args) {
int[] a = {2, 3, 1, 7, 6, 4, 5};
System.out.println(Arrays.toString(a)); // [2, 3, 1, 7, 6, 4, 5]
sort(a);
System.out.println(Arrays.toString(a)); // [1, 2, 3, 4, 5, 6, 7]
}
}
用
PriorityQueue也行，本质是小顶堆，每次poll()一个放到数组里【比上面递归和非递归都慢】
堆排序变体：
/**
* <h3>堆排序变体</h3>
* <p>参考了这篇论文 <a href="https://www.sciencedirect.com/science/article/pii/030439759390364Y">...</a></p>
*
*/
public class HeapSortVariant {
public static void sort(int[] a) {
// 构建大顶堆
heapify(a, a.length);
for (int right = a.length - 1; right > 0; right--) {
int t = a[0];
a[0] = a[right];
a[right] = t;
down(a, 0, right);
}
}
private static void heapify(int[] array, int size) {
for (int i = size / 2 - 1; i >= 0; i--) {
down(array, i, size);
}
}
private static int leaf(int[] array, int start, int size) {
int j = start;
while (true) {
int left = 2 * j + 1;
int right = left + 1;
if(left < size && right < size) {
if (array[right] > array[left]) {
j = right;
} else {
j = left;
}
} else if (left < size) {
j = left;
} else {
break;
}
}
return j;
}
private static int parent(int j) {
return (j - 1) >>> 1;
}
private static void down(int[] array, int start, int size) {
// 返回较大的叶子节点
int leaf = leaf(array, start, size);
while (array[start] > array[leaf]) {
leaf = parent(leaf);
}
int x = array[leaf];
array[leaf] = array[start];
while (leaf > start) {
leaf = parent(leaf);
int t = array[leaf];
array[leaf] = x;
x = t;
}
}
public static void main(String[] args) {
int[] a = {2, 3, 1, 7, 6, 4, 5};
System.out.println(Arrays.toString(a));
sort(a);
System.out.println(Arrays.toString(a));
}
}
4. 插入排序
见笔记001-5.4插入排序（递归版） 扑克牌
分为前面已排序和后面未排序部分，每回合选取未排序的第一个，依次和前面已排序的比较，小于则交换，直到找到合适位置。
要点
- 将数组分为两部分 [0 .. low-1] [low .. a.length-1]
- 左边 [0 .. low-1] 是已排序部分
- 右边 [low .. a.length-1] 是未排序部分
- 每次从未排序区域取出 low 位置的元素, 插入到已排序区域
例
非递归实现代码：
/**
* 插入排序
*/
public class InsertionSort {
public static void sort(int[] a) {
for (int low = 1; low < a.length; low++) { // 最后一个元素也要排序
int t = a[low]; // 未排序的第一个值
int i = low - 1; // 已排序的最后一个值
// 自右向左找插入位置，如果比待插入元素大，则不断右移，空出插入位置
while (i >= 0 && t < a[i]) {
a[i + 1] = a[i];
i--;
}
// 找到插入位置
if (i != low - 1) {
a[i + 1] = t;
}
}
}
public static void main(String[] args) {
int[] a = {9, 3, 7, 2, 5, 8, 1, 4};
System.out.println(Arrays.toString(a)); // [9, 3, 7, 2, 5, 8, 1, 4]
sort(a);
System.out.println(Arrays.toString(a)); // [1, 2, 3, 4, 5, 7, 8, 9]
}
}
递归实现：（自写）
public class InsertionSortRecursion {
public static void sort(int[] a, int unIndex) {
if (unIndex == a.length) { // 最后一个元素也要排序
return;
}
int value = a[unIndex];
int i = unIndex - 1;
while (i >= 0 && a[i] > value) {
a[i + 1] = a[i];
i--;
}
if (i != unIndex - 1) {
a[i + 1] = value;
}
sort(a, unIndex + 1);
}
public static void main(String[] args) {
int[] a = {9, 3, 7, 2, 5, 8, 1, 4};
System.out.println(Arrays.toString(a)); // [9, 3, 7, 2, 5, 8, 1, 4]
sort(a, 1);
System.out.println(Arrays.toString(a)); // [1, 2, 3, 4, 5, 7, 8, 9]
}
}
5. 希尔排序
要点
- 简单的说，就是分组实现插入，每组元素间隙称为
gap - 每轮排序后
gap逐渐变小，直至gap为 1 完成排序 - 对插入排序的优化，让元素更快速地交换到最终位置
下图演示了 gap = 4，gap = 2，gap = 1 的三轮排序前后比较
/**
* 希尔排序
*/
public class ShellSort {
public static void sort(int[] a) {
for (int gap = a.length >> 1; gap >= 1; gap = gap >> 1) {
// low = gap，直接从后半部分开始
// 原来插入排序的代码 1 -> gap
// gap=4，low++相当于换组
for (int low = gap; low < a.length; low++) {
int t = a[low]; // t=5（main示例）
int i = low - gap;
// 自右向左找插入位置，如果比待插入元素大，则不断右移，空出插入位置
while (i >= 0 && t < a[i]) {
a[i + gap] = a[i];
i -= gap;
}
// 找到插入位置
if (i != low - gap) {
a[i + gap] = t;
}
}
}
}
public static void main(String[] args) {
int[] a = {9, 3, 7, 2, 5, 8, 1, 4, 0};
System.out.println(Arrays.toString(a));
sort(a);
// [0, 1, 2, 3, 4, 5, 7, 8, 9]
System.out.println(Arrays.toString(a));
}
}
6. 归并排序
要点：
- 分 - 每次从中间切一刀，处理的数据少一半
- 治 - 当数据仅剩一个时可以认为有序
- 合 - 两个有序的结果，可以进行合并排序（参见笔记001-3.7-数组练习--合并有序数组）
自上至下（递归）：
/**
* <h3>归并排序 TopDown</h3>
*/
public class MergeSortTopDown {
/*
合并：
a1 原始数组
i~iEnd 第一个有序范围
j~jEnd 第二个有序范围
a2 临时数组
*/
public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
int k = i; // i 是 靠左一半的起点
while (i <= iEnd && j <= jEnd) {
if (a1[i] < a1[j]) {
a2[k] = a1[i];
i++;
} else {
a2[k] = a1[j];
j++;
}
k++;
}
if (i > iEnd) {
System.arraycopy(a1, j, a2, k, jEnd - j + 1);
}
if (j > jEnd) {
System.arraycopy(a1, i, a2, k, iEnd - i + 1);
}
}
public static void sort(int[] a1) {
int[] a2 = new int[a1.length];
split(a1, 0, a1.length - 1, a2);
}
private static void split(int[] a1, int left, int right, int[] a2) {
// 调试用
// int[] array = Arrays.copyOfRange(a1, left, right + 1);
// System.out.println(Arrays.toString(array));
// 2. 治
if (left == right) {
return;
}
// 1. 分
int m = (left + right) >>> 1;
split(a1, left, m, a2); // left = 0 m = 0 9
split(a1, m + 1, right, a2); // m+1 = 1 right = 1 3
// 3. 合
merge(a1, left, m, m + 1, right, a2);
// 将排序好的结果重新 覆盖到 a1
System.arraycopy(a2, left, a1, left, right - left + 1);
System.out.println(left + " " + right);
}
public static void main(String[] args) {
int[] a = {9, 3, 7, 2, 8, 5, 1, 4};
System.out.println(Arrays.toString(a));
sort(a);
System.out.println(Arrays.toString(a));
}
}
时间复杂度：
- 两个长度为 m 和 n 的链表合并，时间复杂度是 m + n
- 归并，时间复杂度：
f(n) = 2f(n/2) + n, f(1)=c，等价解f(n) = nlog_2{n} + cn8 / \ 4 4 / \ / \ 2 2 2 2 || || || || 11 11 11 11 f(8) = 2f(4) + 8 f(4) = 2f(2) + 4 f(2) = 2f(1) + 2 f(1) = 1 f(8) = 8 + 24 f(4) = 4 + 8 f(2) = 2 + 2 f(1) = 1- 当 n = 16 时，结果 80
- 当 n = 64 时，结果 448
- 若逐一合并，时间复杂度：
f(n)=\sum\limits_{n=0}^{n-1}n+1，等价解f(n)=\frac{1}{2}(n^2+n)1|0 => 1 1|1 => 2 1|2 => 3 1|3 => 4 1|4 => 5 1|5 => 6 1|6 => 7 1|7 => 8 36- 当 n = 16 时，结果 136
- 当 n = 64 时，结果 2080
自下至上，非递归实现：
merge()方法不变，spilt()方法合并到sort()
/**
* <h3>归并排序 BottomUp</h3>
*/
public class MergeSortBottomUp {
/*
a1 原始数组
i~iEnd 第一个有序范围
j~jEnd 第二个有序范围
a2 临时数组
*/
public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
int k = i;
while (i <= iEnd && j <= jEnd) {
if (a1[i] < a1[j]) {
a2[k] = a1[i];
i++;
} else {
a2[k] = a1[j];
j++;
}
k++;
}
if (i > iEnd) {
System.arraycopy(a1, j, a2, k, jEnd - j + 1);
}
if (j > jEnd) {
System.arraycopy(a1, i, a2, k, iEnd - i + 1);
}
}
public static void sort(int[] a1) {
int n = a1.length;
int[] a2 = new int[n];
// width 代表有序区间的宽度，取值依次为 1、2、4 ...
for (int width = 1; width < n; width *= 2) {
// [left, right] 分别代表待合并区间的左右边界
for (int left = 0; left < n; left += 2 * width) {
//下一组左边界-1 防止越界, 用 left+width 是不可行的，当with=2时，是两组长度为2的数组要合并，因此是width*2
int right = Math.min(left + 2 * width - 1, n - 1);
// System.out.printf("width %d [%d,%d]%n", width, left, right);
int m = Math.min(left + width - 1, n - 1);
merge(a1, left, m, m + 1, right, a2); // m+1超过数组长度的话，merge方法会处理
}
System.arraycopy(a2, 0, a1, 0, n);
}
}
public static void main(String[] args) {
int[] a = {9, 3, 7, 2, 8, 5, 1, 4, 10};
System.out.println(Arrays.toString(a));
sort(a);
System.out.println(Arrays.toString(a));
/*
[9, 3, 7, 2, 8, 5, 1, 4, 10]
width 1 [0,1]
width 1 [2,3]
width 1 [4,5]
width 1 [6,7]
width 1 [8,8]
width 2 [0,3]
width 2 [4,7]
width 2 [8,8]
width 4 [0,7]
width 4 [8,8]
width 8 [0,8]
[1, 2, 3, 4, 5, 7, 8, 9, 10]
*/
}
}
7. 归并+插入
- 小数据量且有序度高时，插入排序效果高
- 大数据量用归并效果好
- 可以结合二者
/**
* <h3>归并排序 + 插入排序</h3>
*/
public class MergeInsertionSort {
/**
* 插入排序
* @param a 数组
* @param left 进行插入排序的数组左边界 索引
* @param right 进行插入排序的数组右边界 索引
*/
public static void insertion(int[] a, int left, int right) {
for (int low = left + 1; low <= right; low++) {
int t = a[low]; // 未排序的第一个值
int i = low - 1; // 已排序的最后一个索引
// 自右向左找插入位置，如果比待插入元素大，则不断右移，空出插入位置
while (i >= left && t < a[i]) {
a[i + 1] = a[i];
i--;
}
// 找到插入位置
if (i != low - 1) {
a[i + 1] = t;
}
}
}
public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
int k = i;
while (i <= iEnd && j <= jEnd) {
if (a1[i] < a1[j]) {
a2[k] = a1[i];
i++;
} else {
a2[k] = a1[j];
j++;
}
k++;
}
if (i > iEnd) {
System.arraycopy(a1, j, a2, k, jEnd - j + 1);
}
if (j > jEnd) {
System.arraycopy(a1, i, a2, k, iEnd - i + 1);
}
}
public static void sort(int[] a1) {
int[] a2 = new int[a1.length];
split(a1, 0, a1.length - 1, a2);
}
private static void split(int[] a1, int left, int right, int[] a2) {
// 2. 治 小数据量用插入排序
if (right - left <= 32) {
// 插入排序
insertion(a1, left, right);
return;
}
// 1. 分
int m = (left + right) >>> 1;
split(a1, left, m, a2);
split(a1, m + 1, right, a2);
// 3. 合
merge(a1, left, m, m + 1, right, a2);
System.arraycopy(a2, left, a1, left, right - left + 1);
}
public static void main(String[] args) {
int[] a = {9, 3, 7, 2, 8, 5, 1, 4};
System.out.println(Arrays.toString(a));
sort(a);
System.out.println(Arrays.toString(a));
}
}
8. 快速排序
单边循环快排（lomuto 洛穆托分区方案）
核心思想：每轮找到一个基准点元素，把比它小的放到它左边，比它大的放到它右边，这称为分区
- 选择最右侧元素作为基准点
j找比基准点小的，i找比基准点大的，一旦找到，二者进行交换- 交换时机：
j找到小的，且与i不相等 i找到 >= 基准点元素后，不应自增
- 交换时机：
- 最后基准点与
i交换，i即为基准点最终索引
例：
i 和 j 都从左边出发向右查找，i 找到比基准点4大的5，j找到比基准点小的2，停下来交换
i 找到了比基准点大的5，j 找到比基准点小的3，停下来交换
j 到达 right 处结束，right 与 i 交换，一轮分区结束。基准点有序，接下来递归左边和右边。
代码：
public class QuickSortLomuto {
public static void sort(int[] a) {
quick(a, 0, a.length - 1);
}
/**
* 递归分区
* @param a 数组
* @param left 左边界
* @param right 右边界
*/
private static void quick(int[] a, int left, int right) {
if (left >= right) {
return;
}
int p = partition(a, left, right); // p代表基准点元素索引
quick(a, left, p - 1);
quick(a, p + 1, right);
}
// 对分区交换排序，返回基准点元素索引，基准点不用再参与遍历
private static int partition(int[] a, int left, int right) {
int pv = a[right]; // 基准点元素值
int i = left;
int j = left;
while (j < right) {
if (a[j] < pv) { // j 找到比基准点小的了, 没找到大的
if (i != j) {
swap(a, i, j);
}
// j走（对比）完i走
i++;
}
// 遇到比基准点大的 i持续停留 不++
// j没找到小的，和找到小的在交换后，都++
j++;
}
swap(a, i, right);
return i;
}
private static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
public static void main(String[] args) {
int[] a = {5, 3, 7, 2, 9, 8, 1, 4};
System.out.println(Arrays.toString(a));
sort(a);
System.out.println(Arrays.toString(a));
}
}
ChatGPT代码：
以最左元素为基准点，从基准点+1位置开始比较。更容易理解。
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low + 1;
for (int j = low + 1; j <= high; j++) {
if (arr[j] < pivot) {
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
// Swap pivot (arr[low]) and arr[i-1]
int temp = arr[low];
arr[low] = arr[i - 1];
arr[i - 1] = temp;
return i - 1;
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println("Sorted array:");
for (int value : arr) {
System.out.print(value + " ");
}
}
}
以上两种代码，leetcode均超时。
双边循环要点：
- 选择最左侧元素作为基准点
j找比基准点小的，i找比基准点大的，一旦找到，二者进行交换i从左向右j从右向左
- 最后基准点与
i交换，i即为基准点最终索引
例：
i 找到比基准点大的5停下来，j 找到比基准点小的1停下来（包含等于），二者交换
i 找到8，j 找到3，二者交换，i 找到7，j 找到2，二者交换
i == j，退出循环，基准点与 i 交换
代码
/**
* <h3>双边循环快排</h3>
* <ol>
* <li>选择最左元素作为基准点元素</li>
* <li>j 指针负责从右向左找比基准点小或等的元素，i 指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至 i，j 相交</li>
* <li>最后基准点与 i（此时 i 与 j 相等）交换，i 即为分区位置</li>
* </ol>
*/
public class QuickSortHoare {
public static void sort(int[] a) {
quick(a, 0, a.length - 1);
}
private static void quick(int[] a, int left, int right) {
if (left >= right) {
return;
}
int p = partition(a, left, right);
quick(a, left, p - 1);
quick(a, p + 1, right);
}
/*
注意事项
1. 为啥要加内层循环的 i<j 条件： 避免一直找不到内层while减过头 超过j
2. 为啥要先处理 j，再处理 i。
j是找小的，i是找大的，当i==j停下来时，会和基准点进行交换，确保是j指向的小的被移到前面（基准点位）
3. 随机元素作为基准点 避免数据不平衡（像是降序数组）提高复杂度
4. 如果有大量重复元素 （例如数组全部值重复）
*/
private static int partition(int[] a, int left, int right) {
// 随机元素
int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left; // +1因为random右边不包
// [0~9] right-left+1=3 [0,2]+4=[4,6]
swap(a, idx, left);
int pv = a[left]; // 没有上面代码，则默认最左边元素为基准点
int i = left;
int j = right;
while (i < j) {
// 1. j 从右向左找小(等)的。先找小的
while (i < j && a[j] > pv) {
j--;
}
// 2. i 从左向右找大的
while (i < j && a[i] <= pv) {
i++;
}
// 3. 交换位置
swap(a, i, j);
}
swap(a, left, i);
return i;
}
private static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
public static void main(String[] args) {
int[] a = {9, 3, 7, 2, 8, 5, 1, 4};
System.out.println(Arrays.toString(a));
sort(a);
System.out.println(Arrays.toString(a));
}
}
随机基准点：
使用随机数作为基准点，避免万一最大值或最小值作为基准点导致的分区不均衡
例：
改进代码：
int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
swap(a, idx, left);
处理重复值：
如果重复值较多，则原来算法中的分区效果也不好，如下图中左侧所示，需要想办法改为右侧的分区效果
改进代码partition()：
/*
循环内
i 从 left + 1 开始，从左向右找大的或相等的
j 从 right 开始，从右向左找小的或相等的
交换，i++ j--
循环外 j 和 基准点交换，j 即为分区位置
*/
private static int partition(int[] a, int left, int right) {
int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
swap(a, left, idx);
int pv = a[left];
// 修改为 left -> left + 1
int i = left + 1;
int j = right;
// 条件多了个等于
while (i <= j) {
// 条件多了个等于
while (i <= j && a[i] < pv) {
i++;
}
// j 从右向左找小的或者【相等】的
while (i <= j && a[j] > pv) {
j--;
}
if (i <= j) {
swap(a, i, j);
i++;
j--;
}
}
swap(a, j, left); // 上面交换后，i索引可能大于j，i数据大于基准点
return j;
}
- 核心思想是
- 改进前，i 只找大于的，j 会找小于等于的。一个不找等于、一个找等于，势必导致等于的值分布不平衡
- 改进后，二者都会找等于的值交换，等于的值会平衡分布在基准点两边
- 细节：
- 因为一开始 i 就可能等于 j
（left + 1 == right），因此外层循环需要加等于条件保证至少进入一次，让 j 能减到正确位置 - 内层 while 循环中 i <= j 的
=也不能去掉，因为 i == j 时也要做一次与基准点的判断，好让 i 及 j 正确 - i == j 时，也要做一次 i++ 和 j-- 使下次循环二者不等才能退出
- 因为最后退出循环时 i 会大于 j，因此最终与基准点交换的是 j
- 因为一开始 i 就可能等于 j
- 内层两个 while 循环的先后顺序不再重要
9. 排序例题
9.1 排序数组
给你一个整数数组
nums，请你将该数组升序排列。
1 <= nums.length <= 5 * 104
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
9.2 排序链表
合并链表见：001-4.3.6 合并有序链表
给你链表的头结点
head，请将其按 升序 排列并返回 排序后的链表 。进阶：你可以在
O(n log n)时间复杂度和常数级空间复杂度下，对链表进行排序吗？
输入：head = [4,2,1,3]
输出：[1,2,3,4]
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
输入：head = []
输出：[]
前言：
「147. 对链表进行插入排序」要求使用插入排序的方法对链表进行排序，插入排序的时间复杂度是O(n^2)，其中n是链表的长度。这道题考虑时间复杂度更低的排序算法。题目的进阶问题要求达到O(nlogn)的时间复杂度和O(1)的空间复杂度，时间复杂度是O(nlogn)的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是O(n^2)，其中最适合链表的排序算法是归并排序。归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现，考虑到递归调用的栈空间，自顶向下归并排序的空间复杂度是
O(logn)。如果要达到O(1)的空间复杂度，则需要使用自底向上的实现方式。链接：https://leetcode.cn/problems/sort-list/solutions/492301/pai-xu-lian-biao-by-leetcode-solution/
方法一：自顶向下归并排序
对链表自顶向下归并排序的过程如下。
- 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
- 对两个子链表分别排序。
- 将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。
上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1，即当链表为空或者链表只包含 1 个节点时，不需要对链表进行拆分和排序。
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head, null);
}
public ListNode sortList(ListNode head, ListNode tail) {
if (head == null) {
return head;
}
// 链表只有一个节点，tail为null
if (head.next == tail) {
head.next = null;
return head;
}
// 快慢指针
ListNode slow = head, fast = head;
// 这里是tail，无法用null判断结束，这里tail有可能是上一轮的mid，mid.next!=null
while (fast != tail) {
slow = slow.next;
fast = fast.next;
if (fast != tail) {
fast = fast.next;
}
}
ListNode mid = slow;
ListNode list1 = sortList(head, mid); // head.next=tail时，head.next会变为null, 见12行
ListNode list2 = sortList(mid, tail);
ListNode sorted = merge(list1, list2);
return sorted;
}
public ListNode merge(ListNode head1, ListNode head2) {
// 哨兵节点
ListNode dummyHead = new ListNode(0);
ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 != null) {
temp.next = temp1;
} else if (temp2 != null) {
temp.next = temp2;
}
return dummyHead.next;
}
}
时间复杂度：
O(nlogn)，其中 n 是链表的长度。空间复杂度：
O(logn)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间。
方法二：自底向上归并排序
使用自底向上的方法实现归并排序，则可以达到 O(1) 的空间复杂度。
首先求得链表的长度 length，然后将链表拆分成子链表进行合并。
具体做法如下：
- 用
subLength表示每次需要排序的子链表的长度，初始时subLength=1。 - 每次将链表拆分成若干个长度为
subLength的子链表（最后一个子链表的长度可以小于subLength，按照每两个子链表一组进行合并，合并后即可得到若干个长度为subLength×2的有序子链表（最后一个子链表的长度可以小于subLength×2。合并两个子链表仍然使用「21. 合并两个有序链表」的做法。 - 将
subLength的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于length，整个链表排序完毕。
class Solution {
public ListNode sortList(ListNode head) {
if (head == null) {
return head;
}
int length = 0;
ListNode node = head;
// 获取链表长度
while (node != null) {
length++;
node = node.next;
}
ListNode dummyHead = new ListNode(0, head);
for (int subLength = 1; subLength < length; subLength <<= 1) {
ListNode prev = dummyHead, curr = dummyHead.next;
while (curr != null) {
ListNode head1 = curr;
// 走完前半段链表长度
for (int i = 1; i < subLength && curr.next != null; i++) {
curr = curr.next;
}
// 来到后半段链表
ListNode head2 = curr.next;
// 断开前半部分链表
curr.next = null;
curr = head2;
// 注意：这里要比上面多判断一次 curr != null
for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
curr = curr.next;
}
// 获取下次的链表
ListNode next = null;
if (curr != null) {
next = curr.next;
// 断开两次链表
curr.next = null;
}
ListNode merged = merge(head1, head2);
prev.next = merged;
while (prev.next != null) {
// 将prev指针移到合并后的链表尾部，方便下次prev.next指向下次合并后的链表，使链表合并
prev = prev.next;
}
curr = next;
}
}
return dummyHead.next;
}
public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummyHead = new ListNode(0);
ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 != null) {
temp.next = temp1;
} else if (temp2 != null) {
temp.next = temp2;
}
return dummyHead.next;
}
}
- 时间复杂度：
O(nlogn)，其中 n 是链表的长度。- 空间复杂度：
O(1)。
四、非比较排序算法
0.对比
| 非比较排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 计数排序 | O(n+k) |
O(n+k) |
稳定 |
| 桶排序 | O(n+k) |
O(n+k) |
稳定 |
| 基数排序 | O(d*(n+k)) |
O(n+k) |
稳定 |
其中
n是数组长度k是桶长度d是基数位数
1. 计数排序
要点：
- 找到最大值，创建一个大小为
最大值+1的count数组。（+1是为了统计数组内等于0的元素出现次数，将值放入0索引） count数组的索引对应原始数组的元素，用来统计该元素的出现次数- 遍历
count数组，根据count数组的索引（即原始数组的元素）以及出现次数，生成排序后内容count数组的索引是：已排序好的
前提：待排序元素 >=0 ，且最大值不能太大
原始数组： {5, 1, 1, 3, 0}
统计数组： [1 2 0 1 0 1] （对应索引值在原始数组的出现次数）
索引： 0 1 2 3 4 5
根据统计数组生成排序后的数组：
[0 1 1 3 5]
改进：
- 让原始数组的【最小值（可以是负数）】映射到
count[0]最大值映射到count最右侧 - 原始数组元素 - 最小值 = count 索引 （最小值是负数的话，相当于非负数部分整体前移，移动长度就是负数的绝对值）
- count 索引 + 最小值 = 原始数组元素
{5, 1, 1, 3, 0, -1} 原始数组 a
数组最小值为-1，相当于让-1的出现次数放到索引0处，0的出现次数放到索引1处，以此类推。
原始数组元素 - 最小值 = count 索引。（0-（-1） = 1），0元素次数放到索引1处
[1 1 2 0 1 0 1 ] count
0 1 2 3 4 5 6 index
-1 0 1 3 5 origin element
// 时间复杂度
// 2N + K （N数组长度，k：max-min+1） 基于比较的排序最优： n*log(n)
代码：
/**
* <h3>计数排序</h3>
*/
public class CountingSort {
public static void main(String[] args) {
int[] a = {5, 1, 1, 3, 0, -1};
System.out.println(Arrays.toString(a));
sort(a);
System.out.println(Arrays.toString(a));
}
public static void sort(int[] a) {
// 获取最值
int max = a[0];
int min = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
if (a[i] < min) {
min = a[i];
}
}
// 获取出现次数的数组
int[] count = new int[max - min + 1]; // 如果min是负数，减负数相当于加正数
for (int v : a) { // v 原始数组元素 - 最小值 = count 索引
count[v - min]++;
}
System.out.println(Arrays.toString(count));
// 将统计数组 转变回 排序结果数组
int k = 0; // 配合源数组a使用的索引值
for (int i = 0; i < count.length; i++) {
// i + min 代表原始数组元素 count[i] 元素出现次数
while (count[i] > 0) {
a[k++] = i + min; // i是索引，要加回最小值
count[i]--;
}
}
}
}
运行力扣912题，即上面的9.1结果：
针对 byte []，因为数据范围已知，省去了求最大、最小值的过程，java 中对 char[]、short[]、byte[] 的排序都可能采用 counting 排序
public static void sort(byte[] a) {
int[] counting = new int[256];
for (int i : a) {
counting[i & 0xFF]++;
}
int k = a.length-1;
for (int i = 128 + 256; k >= 0; ) {
while (counting[--i & 0xFF] ==0);
int v = i & 0xFF;
int c = counting[i & 0xFF];
for (int j = 0; j < c; j++) {
a[k] = (byte) v;
k--;
}
}
}
稳定计数排序：
排序算法(六)：Counting Sort 计数排序 - Aaron Zhu的文章 - 知乎
上面的计数排序算法是非稳定的，而一般我们所说的计数排序都是稳定的。
那么如何保证计数排序的稳定性呢？其实很简单，只需在统计完待排序元素的频数后，对counts作累加计算（counts[i] = counts[i-1] + counts[i]），即计算统计数组中指定索引位置上的元素在排序后的位置；然后倒序遍历原数组，根据counts数组中的排序位置来将待排序元素放入合适的位置，同时将 counts 数组相应的值减1，以使下一个重复的排序元素可以放在前一位的位置上，以保证稳定性。
算法图解
下图即是通过稳定的计数排序对 【-1,1,-1,1,2】序列进行升序排列的图解过程
1. 建立counts数组
2. 倒序遍历原待排序数组，按升序排列
（1）反向遍历，第一次遍历到原数组的2，2存放于统计数组索引3处，统计数组索引3处存储值5，【5表示从小到大排到该数字时一共有5个数，计算索引则-1】5-1=4，表示该值‘2’应该存在索引4处。存放后，值-1，如果有下一个数，则应该排它前面
（2）遍历到1时，1存放于统计数组索引2处，统计数组索引2处存储值4，表示从小到大排到这个‘1’需要4个空间，那么应该存放的索引位置则是3，值-1后放回，下（前）一个1则就存放其前面。
public static void sort2(int[] a) {
int min = a[0];
int max = a[0];
for (int i : a) {
if (i > max) {
max = i;
} else if (i < min) {
min = i;
}
}
int[] counting = new int[max - min + 1];
for (int i : a) {
counting[i - min]++;
}
// 将值位置 与 存放的索引对应
for (int i = 1; i < counting.length; i++) {
counting[i] = counting[i] + counting[i - 1];
}
// 倒序放回
// 因为需要倒序原数组，不能改变其值，所以要新建数组存放
int[] b = new int[a.length];
for (int i = a.length - 1; i >= 0; i--) {
int j = a[i] - min; // 获得统计数组的索引
counting[j]--; // 值减一
b[counting[j]] = a[i]; // 上面-1后就是目标位置
}
System.arraycopy(b, 0, a, 0, a.length);
}
2. 桶排序
思路：将一组数据划分为多个小数组（桶），每个小数组排序后在放回大数组
/* // 假设人类年龄 1~99
按年龄段划分：分段排序
0
1 18
2 20 25 28
3 31 30
4
5
6 66 67
7
8
9
*/
初步实现：
/**
* <h3>桶排序</h3>
*/
public class BucketSort {
public static void main(String[] args) {
int[] ages = {20, 18, 28, 66, 25, 31, 67, 30}; // 假设人类年龄 1~99
System.out.println(Arrays.toString(ages));
sort(ages);
System.out.println(Arrays.toString(ages));
}
public static void sort(int[] ages) {
// 1. 准备桶
// ArrayList也行
// ArrayList<Integer>[] buckets = new ArrayList[10];
DynamicArray[] buckets = new DynamicArray[10];
for (int i = 0; i < buckets.length; i++) {
// buckets[i] = new ArrayList<>();
buckets[i] = new DynamicArray();
}
// 2. 放入年龄数据
for (int age : ages) {
buckets[age / 10].addLast(age);
}
int k = 0;
for (DynamicArray bucket : buckets) {
// 3. 排序桶内元素
int[] array = bucket.array();
InsertionSort.sort(array);
System.out.println(Arrays.toString(array));
// 4. 把每个桶排序好的内容，依次放入原始数组
for (int v : array) {
ages[k++] = v;
}
}
}
}
上面代码缺点：数据可能分布不均匀，假如数据只有0-9，则只有一个数组（桶）有值。
优化方法：借鉴上面的计数排序。桶能承载的数据量=range(参数传入)，桶个数：（max - min）/ range + 1
改进后代码：
/*
桶index range
0 0,1,2
1 3,4,5
2 6,7,8
3 9
*/
public static void sort(int[] a, int range) {
// 获得最值
int max = a[0];
int min = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
if (a[i] < min) {
min = a[i];
}
}
// 1. 准备桶
// 1. 准备桶
// max - min，相当于，一个数据，一个桶。
// range 表示 每个桶能放多少数据
DynamicArray[] buckets = new DynamicArray[(max - min) / range + 1];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new DynamicArray();
}
// 2. 放入数据
for (int age : a) {
// range ： 每个桶能放多少数据
// 桶的索引为 (当前数据 - 最小值) / range
buckets[(age - min) / range].addLast(age);
}
int k = 0;
for (DynamicArray bucket : buckets) {
// 3. 排序桶内元素
int[] array = bucket.array();
InsertionSort.sort(array);
// System.out.println(Arrays.toString(array));
// 4. 把每个桶排序好的内容，依次放入原始数组
for (int v : array) {
a[k++] = v;
}
}
}
使用ArrayList数组实现【自写】：
public class BucketSort_list {
public static void main(String[] args) {
int[] ages = {20, 18, 28, 66, 25, 31, 67, 30}; // 假设人类年龄 1~99
System.out.println(Arrays.toString(ages));
sort(ages, 3);
System.out.println(Arrays.toString(ages));
}
public static void sort(int[] a, int range) {
// 获得最值
int max = a[0];
int min = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
if (a[i] < min) {
min = a[i];
}
}
ArrayList<Integer>[] buckets = new ArrayList[(max - min) / range + 1];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<>();
}
// 放入数据
for (int age : a) {
buckets[(age - min) / range].add(age);
}
int k = 0;
for (ArrayList<Integer> bucket : buckets) {
// System.out.println(bucket);
// 集合 转 数组
Integer[] array = bucket.toArray(new Integer[bucket.size()]);
sort1(array);
for (Integer i : array) {
a[k++] = i;
}
}
}
public static void sort1(Integer[] a) {
for (int low = 1; low < a.length; low++) {
int t = a[low]; // 未排序的第一个值
int i = low - 1; // 已排序的最后一个值
// 自右向左找插入位置，如果比待插入元素大，则不断右移，空出插入位置
while (i >= 0 && t < a[i]) {
a[i + 1] = a[i];
i--;
}
// 找到插入位置
if (i != low - 1) {
a[i + 1] = t;
}
}
}
}
3. 基数排序
对于像手机号这类较长的数据，可以使用基数排序。桶排序先按个位排，再按十位，百位...
String[] phoneNumbers = new String[6];
phoneNumbers[0] = "158";
phoneNumbers[1] = "151";
phoneNumbers[2] = "235";
phoneNumbers[3] = "138";
phoneNumbers[4] = "139";
phoneNumbers[5] = "159";
按个位（0-9）排：
0
1 151
2
3
4
5 135
6
7
8 158 138
9 139 159
结果：
151 135 158 138 139 159
按十位（0-9）排：
0
1
2
3 135 138 139
4
5 151 158 159
6
7
8
9
结果：
135 138 139 151 158 159 按十位排
百位都一样，省略。
代码：
/**
* <h3>基数排序 最低有效数字 LSD(Least significant digit)</h3>
*/
public class RadixSort {
public static void radixSort(String[] a, int length) {
// 1. 准备桶
ArrayList<String>[] buckets = new ArrayList[128]; // 0~127
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<>();
}
// 2. 进行多轮按位桶排序
for (int i = length - 1; i >= 0; i--) {
// 将字符串放入合适的桶
for (String s : a) {
// chatAt不断变化，取不同的值
buckets[s.charAt(i)].add(s);
}
// 重新取出排好序的字符串，放回原始数组
int k = 0;
for (ArrayList<String> bucket : buckets) {
for (String s : bucket) {
a[k++] = s;
}
bucket.clear(); // 清空桶
}
// System.out.println(Arrays.toString(a));
}
}
public static void main(String[] args) {
String[] phoneNumbers = new String[10]; // 0~127
phoneNumbers[0] = "13812345678"; // int long
phoneNumbers[1] = "13912345678";
phoneNumbers[2] = "13612345678";
phoneNumbers[3] = "13712345678";
phoneNumbers[4] = "13512345678";
phoneNumbers[5] = "13412345678";
phoneNumbers[6] = "15012345678";
phoneNumbers[7] = "15112345678";
phoneNumbers[8] = "15212345678";
phoneNumbers[9] = "15712345678";
RadixSort.radixSort(phoneNumbers, 11);
for (String phoneNumber : phoneNumbers) {
System.out.println(phoneNumber);
}
}
}
以上代码，如果从前往后排则【亲测】不行，以三位数为例，从后往前最后一轮（优先级高）比较的是百位。而从前完后，最后一轮比较的是个位。
基数排序是稳定排序，因此先排个位、再排十位，十位的排序不会打乱个位取值相等的元素顺序
4. 排序例题
| 题目编号 | 题目标题 | 排序算法类型 |
|---|---|---|
| 1122 | 数组的相对排序 | 计数排序 |
| 1636 | 按照频率将数组升序排序 | 计数排序 |
| 164 | 最大间距 | 基数排序、桶排序 |
| 315 | 计算右侧小于当前元素的个数 | 基数排序 |
| 347 | 前 K 个高频元素 | 桶排序 |
| 题目编号 | 题目标题 | 排序算法类型 |
|---|---|---|
| 75 | 颜色分类 | 三向切分快速排序 |
| 215 | 数组中的第K个最大元素 | 堆排序 |
| 493 | 翻转对 | 归并排序 |
| 493 | 翻转对 | 树状数组 |
| 524 | 通过删除字母匹配到字典里最长单词 | 循环排序 |
| 977 | 有序数组的平方 | 双指针法 |
4.1 数组的相对排序
给你两个数组，
arr1和arr2。arr2中的元素各不相同，arr2中的每个元素都出现在arr1中。对
arr1中的元素进行排序，使arr1中项的相对顺序和arr2中的相对顺序相同。未在arr2中出现过的元素需要按照升序放在arr1的末尾。
1 <= arr1.length, arr2.length <= 10000 <= arr1[i], arr2[i] <= 1000arr2中的元素arr2[i]各不相同arr2中的每个元素arr2[i]都出现在arr1中
示例 1：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
示例 2:
输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出：[22,28,8,6,17,44]
思路：计数排序
因为题目数据在0-1000内，所以可以创建一个大小1001的
count数组，遍历arr1，出现一次对应数字的索引数据++，再遍历arr2，按顺序取数据，剩下的数据按顺序取出就行。因为索引对应的就是数据，所以结果是递增的。
/*
根据另一个数组次序排序 前提
1. 元素值均 >= 0 <=1000
2. 两个数组长度 <= 1000
*/
public class E01Leetcode1122 {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
// 创建数组，添加arr1元素
int[] count = new int[1001];
for (int i : arr1) {
count[i]++;
}
// System.out.println(Arrays.toString(count));
// tinmes 2, 4, 1 （个）
// index 1 2 3
// 1 1 2 2 2 2 3 原始count排序
// 2 2 2 2 3 1 1 要求的（通过对arr2遍历获得）
int[] result = new int[arr1.length];
int k = 0;
// 按arr2 顺序 输出 所有arr1中包含arr2的数据
for (int i : arr2) {
while (count[i] > 0) {
result[k++] = i;
count[i]--;
}
}
// 索引即数据，索引递增，数据也是递增的。输出所有剩余数据
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
result[k++] = i;
count[i]--;
}
}
return result;
}
public static void main(String[] args) {
int[] arr1 = {3, 2, 1, 2, 2, 1, 2, 5, 4};
int[] arr2 = {2, 3, 1};
E01Leetcode1122 leetcode = new E01Leetcode1122();
int[] result = leetcode.relativeSortArray(arr1, arr2);
System.out.println(Arrays.toString(result));
}
}
4.2 按照频率将数组升序排序
给你一个整数数组
nums，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。请你返回排序后的数组。
1 <= nums.length <= 100-100 <= nums[i] <= 100
示例 1：
输入：nums = [1,1,2,2,2,3]
输出：[3,1,1,2,2,2]
解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。
示例 2：
输入：nums = [2,3,1,3,2]
输出：[1,3,3,2,2]
解释：'2' 和 '3' 频率都为 2 ，所以它们之间按照数值本身降序排序。
示例 3：
输入：nums = [-1,1,-6,4,5,-6,1,4,1]
输出：[5,-1,4,4,-6,-6,1,1,1]
个人解法：两重计数排序
第一次计数排序，索引记录数据，value记录次数。
第二次计数排序，根据上面的统计数组，索引记录次数，value记录数据
public class E1636 {
public int[] frequencySort(int[] nums) {
// index 元素 -> value 次数 -100（索引0） 出现 2 次
int[] count = new int[201];
for (int num : nums) {
count[num + 100]++; // 0对应最小值-100
}
// index 次数 -> value 数据元素
ArrayList<Integer>[] times = new ArrayList[101];
for (int i = 0; i < times.length; i++) {
times[i] = new ArrayList<>();
}
// 对统计数组 进行 计数
for (int i = 0; i < count.length; i++) {
times[count[i]].add(i - 100); // 2次出现 -100 -> 索引2，数值-100
}
int[] ret = new int[nums.length];
int k = 0;
// （出现次数为0的忽略）
for (int i = 1; i < times.length; i++) {
ArrayList<Integer> num_list = times[i];
num_list.sort((a1, a2) -> (a2 - a1)); // 降序排序
for (Integer integer : num_list) {
for (int j = 0; j < i; j++) { // 每个数添加 i 次
ret[k++] = integer;
}
}
}
return ret;
}
public static void main(String[] args) {
int[] nums = {1, 1, 2, 2, 2, 3};
int[] nums1 = {2, 3, 1, 3, 2};
int[] nums2 = {-1, 1, -6, 4, 5, -6, 1, 4, 1};
System.out.println(Arrays.toString(new E1636().frequencySort(nums)));
System.out.println(Arrays.toString(new E1636().frequencySort(nums1)));
System.out.println(Arrays.toString(new E1636().frequencySort(nums2)));
}
}
一次计数排序，使用比较器【用时变慢】：
public int[] frequencySort(int[] nums) {
// 1. 统计出现频率
int[] count = new int[201];
for (int i : nums) {
count[i + 100]++;
}
// 2. 比较器 按频率升序、再按数值降序
return Arrays.stream(nums).boxed().sorted((a, b) -> {
int af = count[a + 100]; // a出现次数
int bf = count[b + 100]; // b出现次数
if (af < bf) {
return -1; // return af - bf
} else if (af > bf) {
return 1;
} else {
return b - a;
}
}).mapToInt(Integer::intValue).toArray();
}
力扣官方题解【Map】：
class Solution {
public int[] frequencySort(int[] nums) {
// <数值, 次数>
Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
for (int num : nums) {
cnt.put(num, cnt.getOrDefault(num, 0) + 1);
}
List<Integer> list = new ArrayList<Integer>();
for (int num : nums) {
list.add(num);
}
// 出现次数不一样，次数递增，出现次数一样，值递减
Collections.sort(list, (a, b) -> {
int cnt1 = cnt.get(a), cnt2 = cnt.get(b);
return cnt1 != cnt2 ? cnt1 - cnt2 : b - a;
});
int length = nums.length;
for (int i = 0; i < length; i++) {
nums[i] = list.get(i);
}
return nums;
}
}
4.3 最大间距
给定一个无序的数组
nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回0。您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。
1 <= nums.length <= 1050 <= nums[i] <= 109
示例 1:
输入: nums = [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:
输入: nums = [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。
方法一：桶排序 - 超过内存限制
public class E03Leetcode164_1 {
public int maximumGap(int[] nums) {
// 1. 处理特殊情况
if (nums.length < 2) {
return 0;
}
// 2. 桶排序
int max = nums[0];
int min = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
}
if (nums[i] < min) {
min = nums[i];
}
}
// 1. 准备桶
DynamicArray[] buckets = new DynamicArray[(max - min) / 1 + 1];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new DynamicArray();
}
// 2. 放入数据
for (int age : nums) {
buckets[(age - min) / 1].addLast(age);
}
int k = 0;
for (DynamicArray bucket : buckets) {
// 3. 排序桶内元素
int[] array = bucket.array();
InsertionSort.sort(array);
// System.out.println(Arrays.toString(array));
// 4. 把每个桶排序好的内容，依次放入原始数组
for (int v : array) {
nums[k++] = v;
}
}
// System.out.println(Arrays.toString(nums));
// 3. 寻找最大差值
int r = 0;
for (int i = 1; i < nums.length; i++) {
r = Math.max(r, nums[i] - nums[i - 1]);
}
return r;
}
public static void main(String[] args) {
// int[] nums = {9, 1, 3, 5};
int[] nums = {1, 10000000}; // 内存超标
int r = new E03Leetcode164_1().maximumGap(nums);
System.out.println(r);
}
}
方法2：基数排序
public class E03Leetcode164_2 {
public int maximumGap(int[] nums) {
// 1. 处理特殊情况
if (nums.length < 2) {
return 0;
}
// 2. 基数排序
// 2.1 准备工作
// int max = Arrays.stream(array).max().getAsInt();
int max = nums[0]; // 最大值
for (int i = 1; i < nums.length; i++) {
max = Math.max(max, nums[i]);
}
ArrayList<Integer>[] buckets = new ArrayList[10]; // 数字0-9
for (int i = 0; i < 10; i++) {
buckets[i] = new ArrayList<>();
}
// 2.2 一轮基数排序 O(6n) O(n)
int m = 1;
while(m <= max) {
for (int i : nums) {
buckets[i / m % 10].add(i); // 求个 十 百 千 位 除10 100 1000
}
int k = 0;
for (ArrayList<Integer> bucket : buckets) {
// System.out.println(bucket);
for (Integer i : bucket) {
nums[k++] = i;
}
bucket.clear();
}
System.out.println(Arrays.toString(nums));
m = m * 10;
}
// 3. 寻找最大差值
int r = 0;
for (int i = 1; i < nums.length; i++) {
r = Math.max(r, nums[i] - nums[i - 1]);
}
return r;
}
// 4233 / 10 = 423 % 10 = 3
// 4233 / 100 = 42 % 10 = 2
// 4233 / 1000 = 4 % 10 = 4
// 4233 / 10000 = 0 % 10 = 0
/*
0 11 13 16 26
1 100000
2
3
4
5
6
7
8
9
100000 11 13 26 16 个位排序结果
100000 11 13 16 26 十位排序结果
11 13 16 26 100000 最终排序结果
*/
public static void main(String[] args) {
int[] nums = {26, 16, 13, 11, 100000};
int r = new E03Leetcode164_2().maximumGap(nums);
System.out.println(r);
}
}
力扣题解：基数排序（稳定版）
public class E164_leet1 {
public int maximumGap(int[] nums) {
int n = nums.length;
if (n < 2) {
return 0;
}
long exp = 1;
int[] buf = new int[n];
int maxVal = Arrays.stream(nums).max().getAsInt();
while (maxVal >= exp) {
int[] cnt = new int[10];
for (int num : nums) {
int digit = (num / (int) exp) % 10;
cnt[digit]++;
}
for (int i = 1; i < 10; i++) { // 稳定的计数排序（个位有序，十位有序，百位有序）
cnt[i] += cnt[i - 1];
}
for (int i = n - 1; i >= 0; i--) { // 倒序遍历
int digit = (nums[i] / (int) exp) % 10;
buf[cnt[digit] - 1] = nums[i];
cnt[digit]--;
}
// 一轮排序结束
System.arraycopy(buf, 0, nums, 0, n);
exp *= 10;
}
int ret = 0;
for (int i = 1; i < n; i++) {
ret = Math.max(ret, nums[i] - nums[i - 1]);
}
return ret;
}
public static void main(String[] args) {
// int[] nums = {1, 10000000};
int[] nums = {9, 1, 3, 5, 13};
// int[] nums = {1, 1, 1, 1};
// int[] nums = {1, 1, 1, 1, 1, 5, 5, 5, 5, 5};
// int[] nums = {15252, 16764, 27963, 7817, 26155, 20757, 3478, 22602, 20404, 6739, 16790, 10588, 16521, 6644, 20880, 15632, 27078, 25463, 20124, 15728, 30042, 16604, 17223, 4388, 23646, 32683, 23688, 12439, 30630, 3895, 7926, 22101, 32406, 21540, 31799, 3768, 26679, 21799, 23740};
/*
有没有可能，桶内元素的间距比桶间元素间距还大？ 有空桶
[10] 9
[19 25] 6
*/
// int[] nums = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 220};
int r = new E164_leet1().maximumGap(nums);
System.out.println(r);
}
}
- 时间复杂度：
O(N)，其中N是数组的长度。- 空间复杂度：
O(N)，其中N是数组的长度。
方法三：桶排序 - 合理化桶个数
以下代码放入力扣跑，内存占用上有优势，时间上比
ArrayList集合数组，每个集合转为数组再排序实现还要慢许多
桶个数 期望桶个数
(max - min) / range + 1 = nums.length
所以有：
(max - min) / (nums.length - 1) = range
public class E03Leetcode164_3 {
public int maximumGap(int[] nums) {
// 1. 处理特殊情况
if (nums.length < 2) {
return 0;
}
// 2. 桶排序
int max = nums[0];
int min = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
}
if (nums[i] < min) {
min = nums[i];
}
}
// 2.1 准备桶
// 如果 max - min < nums.length-1 可能发生错误（除0异常）
int range = Math.max((max - min) / (nums.length - 1), 1);
DynamicArray[] buckets = new DynamicArray[(max - min) / range + 1];
// ArrayList集合数组方式
// ArrayList<Integer>[] buckets = new ArrayList[(max - min) / range + 1];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new DynamicArray();
}
// 2.2 放入数据
for (int age : nums) {
buckets[(age - min) / range].addLast(age);
}
int k = 0;
for (DynamicArray bucket : buckets) {
// 2.3 排序桶内元素
// 使用 bucket.sort方法 力扣运行极慢
// Integer[] array = bucket.toArray(new Integer[bucket.size()]);
int[] array = bucket.array();
InsertionSort.sort(array);
System.out.println(Arrays.toString(array));
// 2.4 把每个桶排序好的内容，依次放入原始数组
for (int v : array) {
nums[k++] = v;
}
}
// 3. 寻找最大差值
int r = 0;
for (int i = 1; i < nums.length; i++) {
r = Math.max(r, nums[i] - nums[i - 1]);
}
return r;
}
public static void main(String[] args) {
// int[] nums = {1, 10000000};
// int[] nums = {9, 1, 3, 5};
// int[] nums = {1, 1, 1, 1};
int[] nums = {1, 1, 1, 1, 1, 5, 5, 5, 5, 5};
// int[] nums = {15252, 16764, 27963, 7817, 26155, 20757, 3478, 22602, 20404, 6739, 16790, 10588, 16521, 6644, 20880, 15632, 27078, 25463, 20124, 15728, 30042, 16604, 17223, 4388, 23646, 32683, 23688, 12439, 30630, 3895, 7926, 22101, 32406, 21540, 31799, 3768, 26679, 21799, 23740};
int r = new E03Leetcode164_3().maximumGap(nums);
System.out.println(r);
}
}
解法4：在解法3的基础上，只保留桶内最大最小值
桶内的数据间隔较小，桶之间的数据间隔较大时，可以不用求桶内间距
通过包装类记录每个桶的最大和最小值，用于求桶之间差值
public class E03Leetcode164_4 {
public int maximumGap(int[] nums) {
// 1. 处理特殊情况
if (nums.length < 2) {
return 0;
}
// 2. 桶排序
int max = nums[0];
int min = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
}
if (nums[i] < min) {
min = nums[i];
}
}
// 2.1 准备桶
/*
计算桶个数 期望桶个数 (多一个，空桶)
(max - min) / range + 1 = nums.length + 1
(max - min) / range = nums.length
*/
int range = Math.max((max - min) / nums.length, 1); // 让桶的个数比元素多一个
int bucketSize = (max - min) / range + 1;
// System.out.println("range:" + range + " 桶个数" + bucketSize);
Pair[] buckets = new Pair[bucketSize];
// 2.2 放入数据
for (int v : nums) {
int idx = (v - min) / range; // 索引
if (buckets[idx] == null) {
buckets[idx] = new Pair();
}
buckets[idx].add(v);
}
/* for (Pair bucket : buckets) {
System.out.println(bucket);
}*/
/*
[12,10] 0
[22,20] 1
[30,30] 2
null 3
[40,40] 4
*/
// 3. 寻找最大差值
int r = 0;
int lastMax = buckets[0].max; // 上一个桶的最大值
for (int i = 1; i < buckets.length; i++) {
Pair bucket = buckets[i];
if (bucket != null) {
r = Math.max(r, bucket.min - lastMax);
lastMax = bucket.max;
}
}
return r;
}
// 数据范围 0 <= nums[i] <= 1000_000_000
static class Pair {
int max = 0;
int min = 1000_000_000;
void add(int v) { // 桶内最大最小
max = Math.max(v, max);
min = Math.min(v, min);
}
@Override
public String toString() {
return "[" + max +
"," + min +
']';
}
}
public static void main(String[] args) {
// int[] nums = {1, 10000000};
// int[] nums = {9, 1, 3, 5};
// int[] nums = {1, 1, 1, 1};
// int[] nums = {1, 1, 1, 1, 1, 5, 5, 5, 5, 5};
// int[] nums = {15252, 16764, 27963, 7817, 26155, 20757, 3478, 22602, 20404, 6739, 16790, 10588, 16521, 6644, 20880, 15632, 27078, 25463, 20124, 15728, 30042, 16604, 17223, 4388, 23646, 32683, 23688, 12439, 30630, 3895, 7926, 22101, 32406, 21540, 31799, 3768, 26679, 21799, 23740};
/*
有没有可能，桶内元素的间距比桶间元素间距还大？ 有空桶
[10] 9
[19 25] 6
*/
int[] nums = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 220};
int r = new E03Leetcode164_4().maximumGap(nums);
System.out.println(r);
}
}
力扣解法二，与上诉思路一致：
思路与算法
设长度为 N 的数组中最大值为 max,min，则不难发现相邻数字的最大间距不会小于 ⌈(max−min)/(N−1)⌉
为了说明这一点，我们使用反证法：假设相邻数字的间距都小于 ⌈(max−min)/(N−1)⌉，并记数组排序后从小到大的数字依次为A_1,A_2,...,A_N，则有：
但根据A_1, A_N的定义，一定有 A_1=min，且 A_N = max，故上式会导出矛盾。
因此，我们可以选取整数 d = ⌈(max−min)/(N−1)⌉ < ⌈(max−min)/(N−1)⌉。随后，我们将整个区间划分为若干个大小为 d 的桶，并找出每个整数所在的桶。根据前面的结论，能够知道，元素之间的最大间距一定不会出现在某个桶的内部，而一定会出现在不同桶当中。
因此，在找出每个元素所在的桶之后，我们可以维护每个桶内元素的最大值与最小值。随后，只需从前到后不断比较相邻的桶，用后一个桶的最小值与前一个桶的最大值之差作为两个桶的间距，最终就能得到所求的答案。
4.4 前 K 个高频元素
给你一个整数数组
nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
题目最终需要返回的是前 k 个频率最大的元素，可以想到借助堆这种数据结构，对于 k 频率之后的元素不用再去处理，进一步优化时间复杂度。
- 借助 哈希表 来建立数字和其出现次数的映射，遍历一遍数组统计元素的频率
- 维护一个元素数目为 k 的最小堆
- 每次都将新的元素与堆顶元素（堆中频率最小的元素）进行比较
- 如果新的元素的频率比堆顶端的元素大，则弹出堆顶端的元素，将新的元素添加进堆中
- 最终，堆中的 k 个元素即为前 k 个高频元素
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
// 使用字典，统计每个元素出现的次数，
// 元素为键，元素出现的次数为值
HashMap<Integer,Integer> map = new HashMap();
for(int num : nums){
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
// 最小堆，设定比较顺序
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return map.get(a) - map.get(b);
}
});
// 遍历map，用最小堆保存频率最大的k个元素
for (Integer key : map.keySet()) {
if (pq.size() < k) {
pq.add(key);
} else if (map.get(key) > map.get(pq.peek())) {
pq.remove();
pq.add(key);
}
}
// 取出最小堆中的元素
List<Integer> res = new ArrayList<>();
while (!pq.isEmpty()) {
res.add(pq.remove());
}
return res;
}
}
解法二：桶排序法
首先依旧使用哈希表统计频率，统计完成后，创建一个数组，将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标即可。
//基于桶排序求解「前 K 个高频元素」
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> res = new ArrayList();
// 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
HashMap<Integer,Integer> map = new HashMap();
for(int num : nums){
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
// 桶排序
// 将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标
// 假如数组长度是100，并且全是1，那么索引范围为0-100，长度+1
List<Integer>[] list = new List[nums.length+1];
for(int key : map.keySet()){
// 获取出现的次数作为下标
int i = map.get(key);
if(list[i] == null){
list[i] = new ArrayList();
}
list[i].add(key);
}
// 倒序遍历数组获取出现顺序从大到小的排列
for(int i = list.length - 1; i >= 0 && res.size() < k; i--){
if(list[i] == null) continue;
res.addAll(list[i]);
}
return res;
}
}
五、Java中的排序
Arrays.sort
JDK 7~13 中的排序实现
| 排序目标 | 条件 | 采用算法 |
|---|---|---|
| int[] long[] float[] double[] | size < 47 | 混合插入排序 (pair) |
| size < 286 | 双基准点快排 | |
| 有序度高 | 归并排序 | |
| 有序度低 | 双基准点快排 | |
| byte[] | size > 29 | 计数排序 |
| size <= 29 | 插入排序 | |
| char[] short[] | size > 3200 | 计数排序 |
| size < 47 | 插入排序 | |
| size < 286 | 双基准点快排 | |
| 有序度高 | 归并排序 | |
| 有序度低 | 双基准点快排 | |
| Object[] | -Djava.util.Arrays.useLegacyMergeSort=true | 传统归并排序 |
| TimSort |
JDK 14~20 中的排序实现
| 排序目标 | 条件 | 采用算法 |
|---|---|---|
| int[] long[] float[] double[] | size < 65 并不是最左侧 | 混合插入排序 (pin) |
| size < 44 并位于最左侧 | 插入排序 | |
| 递归次数超过 384 | 堆排序 | |
| 对于整个数组或非最左侧 size > 4096，有序度高 | 归并排序 | |
| 有序度低 | 双基准点快排 | |
| byte[] | size > 64 | 计数排序 |
| size <= 64 | 插入排序 | |
| char[] short[] | size > 1750 | 计数排序 |
| size < 44 | 插入排序 | |
| 递归次数超过 384 | 计数排序 | |
| 不是上面情况 | 双基准点快排 | |
| Object[] | -Djava.util.Arrays.useLegacyMergeSort=true | 传统归并排序 |
| TimSort |
- 其中 TimSort 是用归并+二分插入排序的混合排序算法
- 值得注意的是从 JDK 8 开始支持 Arrays.parallelSort 并行排序
- 根据最新的提交记录来看 JDK 21 可能会引入基数排序等优化
Comments NOTHING