【算法自由之路】前缀树 & 桶排序之计数排序和基数排序

前缀树（字典树）

首先是前缀树，前缀树是由字符构成的树结构，它记录有多少前缀字符通过，以及有多少个同样的字符串，其找这类信息的时间复杂度是极快的，只与字符串本身长度有关，是 O(logK) 级别，K 为字符串长度，可以应用于一些列前缀问题中。

有些抽象，举一个经典的例子，给定一组仅小写字母组成的字符串，如何构建前缀树？

["abc","adui","abd","bcd","af"] 

这个数组构建出来的前缀树是这样的， pass 记录的是有多少个字符串通过了它，end 记录的是有多少字符串以该节点字符结尾

基本的方法有：

向前缀树中添加一个字符串 insert

查找某个字符串在前缀树中数量 getNum

查找有多少字符串以某个前缀开头 getPrfixNum

向前缀树中删除一个字符串 delete

package algorithmic.base;import com.sun.tools.javac.util.StringUtils;import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;/*** @program: algorithmic-total-solution* @description: 字典树* @author: wangzibin* @create: 2022-11-26**/
public class TrieTree {private Node root;public TrieTree() {root = new Node();}private static class Node {int pass;int end;Map next;public Node() {this.pass = 0;this.end = 0;this.next = new HashMap<>();}}public void insert(String str) {if (str == null || str.length() < 1) {return;}int length = str.length();Node current = root;root.pass++;for (int i = 0; i < length; i++) {char c = str.charAt(i);int index = c - 'a';Node node = current.next.get(index);if (node == null) {node = new Node();current.next.put(index, node);}node.pass++;current = node;}current.end++;}public void delete(String str) {if (getNum(str) == 0) {return;}int length = str.length();Node current = root;root.pass--;for (int i = 0; i < length; i++) {char c = str.charAt(i);int index = c - 'a';Node node = current.next.get(index);node.pass--;if (node.pass == 0){// 当某个通路 pass 已经是 0 则直接 remove 完成 deletecurrent.next.remove(index);return;}current = node;}current.end--;}public int getNum(String str) {if (str == null || str.length() < 1) {return 0;}int length = str.length();Node current = root;for (int i = 0; i < length; i++) {char c = str.charAt(i);int index = c - 'a';Node node = current.next.get(index);if (node == null) {return 0;}current = node;}return current.end;}public int getPrefixNum(String str) {if (str == null || str.length() < 1) {return 0;}int length = str.length();Node current = root;for (int i = 0; i < length; i++) {char c = str.charAt(i);int index = c - 'a';Node node = current.next.get(index);if (node == null) {return 0;}current = node;}return current.pass;}public static void main(String[] args) {TrieTree trieTree = new TrieTree();trieTree.insert("abccd");trieTree.insert("abccd");trieTree.insert("abccd");trieTree.insert("abccd");trieTree.insert("abccd");trieTree.insert("abccde1123%^$$8*吧");trieTree.insert("abccdf");trieTree.insert("abccdq");System.out.println(trieTree.getNum("abccde1123%^$$8*吧"));System.out.println(trieTree.getPrefixNum("abccde1123%^$$"));System.out.println(trieTree.getNum("abccd"));System.out.println(trieTree.root.pass);trieTree.delete("abccde1123%^$$8*吧");trieTree.delete("abccde");trieTree.delete("abccd");trieTree.delete("abccd");trieTree.delete("abccd");trieTree.delete("abccd");trieTree.delete("abccd");trieTree.delete("abccd");System.out.println(trieTree.getPrefixNum("abccde1123%^$$8*吧"));System.out.println(trieTree.getPrefixNum("abccde1123%^$$"));System.out.println(trieTree.getNum("abccd"));System.out.println(trieTree.root.pass);}}

如上 Node 节点记录了 pass 和 end 数量，在解决某些前缀问题时或可增加一些特性属性来进行解答。

桶排序

这里桶排序是一种统称，桶即指容器，这个容器可以是 Java 中的数组、链表、哈希表，只要是可以容纳一部分数据的结构都可以称为容器，或者桶。

计数排序、基数排序都是桶排序的一种，它们是不基于比较的排序，它们的排序时间复杂度可以达到 O(N) ，但其对排序数据本身要求比较苛刻，可使用场景有限。

计数排序

顾名思义：统计数据。

比如有这样一个场景，人口普查统计年龄，给所有人的年龄排序，基本上我们可以认为，人的年龄在 0 - 200 之间。

这个时候我们可以准备一个 200 个长度的数组，然后遍历年龄，年龄对应数组下标，遇到一个则 +1，最后遍历数组反向生成排序好的数组。

数组每个下标就是一个桶记录这个桶中有多少个数。

可以见得，这个对数据本身要求很高，比如我的数据如果变了取值范围，达到上亿的值，那准备上亿长度的数组显然不现实，同时就算可以，遍历这个数组的成本也不可忽略。

基数排序

基数:所谓基数,就是进位计数制的每位数上可能有的数码的个数

基数排序一般要求数据是十进制正整数，它是基于分配的排序，根据位数对数据进行分桶最终实现排序。

思路是，十进制，准备十个桶分别代表 0 1 2 3 …… 9 ，所有数据高位根据最大长度数补齐 0

比如

[193,21,33,34,5]
// 补齐后，这里不一定是真的补齐成字符串哈，实现看自己
[193,021,033,034,005]

有几位就进行几次分配入桶，先从低位入桶，这个桶是先进先出队列，这一位数字是几就进几号桶，然后从 0 号桶依次出桶，最终排序完成，这个其实是利用了高位数高于低位的优先级进行的分配排序

对于基数排序，有一个很有意思的实现，即我们不需要真的准备 10 个这样的桶，只需要一个长度为 10 的数组即可。

这个数组每个下标位表示小于等于该位的数有几个，从后往前遍历原数组，取当前位，找到当前数小于等于当前位的数总共有 x 个，根据之前先进先出原则，此时是从后遍历，可以推算出当前数弹出时位置即 arr[x-1] 这个位置

package algorithmic.base;import util.RandomUtil;import java.util.Arrays;
import java.util.Random;/*** @program: algorithmic-total-solution* @description:* @author: wangzibin* @create: 2022-11-28**/
public class RadixSort {public static void sort(int[] arr) {if (arr == null || arr.length < 2) {return;}int len = arr.length;int digit = 0;for (int i = 0; i < len; i++) {digit = Math.max(digit, getDigitNum(arr[i]));}int[] help = new int[len];for (int i = 0; i < digit; i++) {int[] count = new int[10];// 计算 i 位 等于 j 的有多少for (int j = 0; j < len; j++) {count[getDigit(arr[j], i)]++;}// 计算出 i 位 小于等于 j 的有多少for (int j = 1; j < 10; j++) {count[j] = count[j] + count[j - 1];}for (int j = len - 1; j >= 0; j--) {// 模拟先进先出，int currentD = getDigit(arr[j], i);int num = count[currentD];help[num - 1] = arr[j];count[currentD]--;}for (int j = 0; j < len; j++) {arr[j] = help[j];}}}private static int getDigitNum(int num) {int i = 0;while (num > 0) {num /= 10;i++;}return i;}private static int getDigit(int num, int digit) {for (int i = 0; i < digit; i++) {num /= 10;}return num % 10;}public static void main(String[] args) {int[] arr;int[] arr2;SelectionSort selectionSort = new SelectionSort();Random random = new Random();for (int i = 0; i < 1000; i++) {int len = random.nextInt(20) + 5;arr = new int[len];arr2 = new int[len];for (int j = 0; j < len; j++) {int item = random.nextInt(100);arr[j] = item;arr2[j] = item;}sort(arr);selectionSort.sort(arr2);for (int k = 0; k < len; k++) {if (arr[k] != arr2[k]) {System.out.println(Arrays.toString(arr));System.out.println(Arrays.toString(arr2));System.out.println("error " + i);return;}}}System.out.println("success");}
}