07、算法与数据结构 - 实战:前缀树,计数排序与桶排序

前缀树

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;
    }

}