前缀树
Trie
1、 根据字符串数组中,每个字符串的字符作为路径,组成而成的一个多叉树结构;
2、 每个节点都有一个paths数组,表示字符路径;
3、 每个节点都会记录有多少个字符串经过该节点,记为pass;
4、 每个节点都会记录有多少个字符串以该节点结尾,记为end;
这种结构的好处就是查询一个字符串是否存在,或者判断有多少个字符串以某个字符串作为前缀,时间复杂度是O(K),K是指该字符串的长度
/**
* 前缀树
* Created by huangjunyi on 2022/11/20.
*/
public class Trie01 {
private static class Node {
int pass; // 有多少个字符串经过该节点
int end; // 有多少个字符串以该节点结尾
Node[] paths; // 字符路径
public Node() {
pass = 0;
end = 0;
paths = new Node[26];
}
}
private Node root;
public Trie01() {
root = new Node();
}
/**
* 往前缀树中插入字符串
* @param str
*/
public void insert(String str) {
if (str == null) return;
char[] chs = str.toCharArray();
Node node = this.root;
node.pass++;
for (int i = 0; i < chs.length; i++) {
// 如果没有路,先建出路来
if (node.paths[chs[i] - 'a'] == null) node.paths[chs[i] - 'a'] = new Node();
// 沿途pass++
node.paths[chs[i] - 'a'].pass++;
node = node.paths[chs[i] - 'a'];
}
// 结尾字符路径连接的节点,end++
node.end++;
}
public void delete(String str) {
if (search(str) == 0) return;
char[] chs = str.toCharArray();
Node node = this.root;
node.pass--;
for (int i = 0; i < chs.length; i++) {
// 如果沿途发现有节点pass减到0,直接置为null,返回
if (--node.paths[chs[i] - 'a'].pass == 0) {
node.paths[chs[i] - 'a'] = null;
return;
}
node = node.paths[chs[i] - 'a'];
}
// 结尾字符路径连接的节点,end--
node.end--;
}
/**
* 一个字符串在前缀树中出现了几次
* @param str
* @return
*/
public int search(String str) {
if (str == null) return 0;
char[] chs = str.toCharArray();
Node node = this.root;
for (int i = 0; i < chs.length; i++) {
// 根据字符路径,顺着往下走,没路了就返回
if (node.paths[chs[i] - 'a'] == null) return 0;
else node = node.paths[chs[i] - 'a'];
}
// 到达终点,返回end
return node.end;
}
/**
* 一个前缀串在前缀树中出现了几次
* @param prefix
* @return
*/
public int prefixNumber(String prefix) {
if (prefix == null) return 0;
char[] chs = prefix.toCharArray();
Node node = this.root;
for (int i = 0; i < chs.length; i++) {
// 根据字符路径,顺着往下走,没路了就返回
if (node.paths[chs[i] - 'a'] == null) return 0;
else node = node.paths[chs[i] - 'a'];
}
return node.pass;
}
}
计数排序
计数排序时不基于比较的排序算法中的一种,在给定的样本范围比较小的时候,可以采用这种算法,效率会比较高
比如给定一个员工年龄数组,要求根据年龄从大到小进行排序,假设员工年龄的范围是0~200
那么定义一个长度为201的数组help,代表年龄范围,[0]表示0岁的员工有多少个,[1]表示1岁的员工有多少个
然后遍历员工数组,根据员工年龄,help数组对应的年龄+1
然后在根据help数组,把年龄拷贝回年龄数组中,就得到有序的年龄数组
时间复杂度为O(N),因为只需要遍历一遍数组
/**
* 计数排序
*/
public class CountSort01 {
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) return;
//找出数组中最大的数
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
max = Math.max(arr[i], max);
}
//创建一个辅助数组
int[] help = new int[max + 1];
//遍历待排序的数组,值作为help数组的下标,help数组中的值+1
for (int i = 0; i < arr.length; i++) {
help[arr[i]]++;
}
//根据help数组,把数拷贝回原数组
int index = 0;
for (int i = 0; i < help.length; i++) {
for (int j = 0; j < help[i]; j++) {
arr[index++] = i;
}
}
}
}
桶排序
普通桶排序
桶排序是计数排序的一种应用。从低数位开始直到高数位,每次遍历数组中的每一个数,以对应数位上的数作为下标,把当前数放入到该下标指定的队列中,然后在遍历每一个队列,弹出放回到原数组。
1、 按个位排序:;
2、 按十位排序;
3、 按百位排序;
但是这种方法的比较耗费空间,需要准备十个队列,可以做出如下优化。
优化后的桶排序
1、 假设当前数位为d;
2、 遍历数组每一个数的d数位上的数,创建一个count数组,记录d数位上的数出现的次数,count[i]此时就是d数位上的数为i的出现了几次;
3、 遍历count数组,累加前缀和,count[i]此时就是d数位上的数小于等于i的,出现了几次;
4、 创建一个help数组,从后往前遍历原数组,得出d数位上的数i,然后根据count[i]得知,d数位上的数小于等于i的有count[i]个,则在数组help下标为count[i]-1的位置放入当前遍历的数,然后count[i]减一,表示d数位上的数小于等于i的还剩count[i]-1个没处理;
桶排序优化举例
现在要对数组[103,230,107,246,23,17,1]进行排序
现在先进行个位的排序
1、计算count数组
count:[1, 1, 0, 2, 0, 0, 1, 2, 0, 9]
count[0] = 1,表示个位数为0的数,有1个
count[1] = 1,表示个位数为1的数,有1个
count[2] = 0,表示个位数为2的数,有0个
…
count[7] = 2,表示个位数为7的数,有2个
2、把count数组转换为前缀和数组
count:[1, 2, 2, 4, 4, 4, 5, 7, 7, 9]
count[0] = 1,表示个位数<=0的数,有1个
count[1] = 2,表示个位数<=1的数,有2个
count[2] = 2,表示个位数<=2的数,有2个
…
count[7] = 7,表示个位数<=7的数,有7个
3、定义一个help数组,从后往前遍历原数组,根据count数组,确定放入help数组中的位置
遍历到1,个位数为1,count[1]=2,那么放入的位置就是1(count[1]-1 = 2-1),help[1]=1,然后count[1]–
遍历到17,个位数为7,count[7] = 7,那么放入的位置就是6(count[7]-1 = 7-1),help[6]=17,然后count[7]–
依次类推
4、然后把help数组拷贝回原数组arr
这种方式的就比真正建十个队列的方式要节省空间,只要建一个长度为10的count数组,建一个长度和原数组arr相同的help数组
代码:优化后的桶排序
/**
* 桶排序:计数排序的一种应用
*/
public class CountSort02 {
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) return;
//取得当前数组最大值的位数
int maxBit = getMaxBit(arr);
//创建一个辅助数组
int[] help = new int[arr.length];
for (int i = 1; i <= maxBit; i++) {
int[] count = new int[10];
for (int j = 0; j < arr.length; j++) {
//获取数组中每个值指定位上的数
int bitNum = getBitNum(arr[j], i);
//count数组此时记录指定数位上不同数字出现的次数
count[bitNum]++;
}
for (int j = 1; j < count.length; j++) {
//count数组变成指定数位上数字小于等于j的数的个数有几个
count[j] += count[j - 1];
}
//根据count数组的记录,从原数组的最后一位往前遍历,放入help数组中的指定位置
for (int j = arr.length - 1; j >= 0; j--) {
int bitNum = getBitNum(arr[j], i);
//count[bitNum]记录了当前数位i上数字小于等于bitNum的数,出现的次数
//所以arr[j]放入到help数组中count[bitNum]-1的位置
help[count[bitNum] - 1] = arr[j];
//处理过了,减一,下次遇到指定数位上数字相同的数,就会放到前一个位置
count[bitNum]--;
}
//help数组拷贝回原数组
for (int j = 0; j < help.length; j++) {
arr[j] = help[j];
}
}
}
private static int getBitNum(int num, int bit) {
for (int i = 0; i < bit - 1; i++) {
num /= 10;
}
int help = (num / 10) * 10;
return num - help;
}
private static int getMaxBit(int[] arr) {
//找出数组中最大的数
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
max = Math.max(arr[i], max);
}
int res = 0;
while (max != 0) {
max /= 10;
res++;
}
return res;
}
}