image.png

多叉树


image.png
p - pass 经过该结点的字符串个数
e - end 以该结点结束的字符串个数

比hash表强在可以查找前缀

hash表的增删改查是O（1），但是计算hash本身要遍历计算key的hash，所以时间代价是o(k)，k是key的长度。

前缀树的添加代价是o(m),m是字符串的长度，查询代价是o(k)，k是前缀的长度。

代码设计：
准备头结点（伪结点作为起点）
—
前缀树结点类型。
Node[] nexts; // 子结点。字符数量不多，可以用new Node[26]来表示a-z种结点类型。
int pass ；
int end
—

计数排序 — 桶排序
统计员工各年龄排序。（桶排序，不基于排序，年龄发到桶里，这里的桶是0 1 2 … 100 岁）。
桶排序的桶应该是有限。
image.png

基于比较排序 — O（NlogN）顶好，桶排序—-可能做到o(N)

计数排序（属于桶排序）
流程：
元素位数一致（若有负数，可以加一个正值，都不影响排序）
准备桶 ： 根据个位数进桶，再按桶顺序到倒出桶； 再根据十位数进桶倒桶；。。。。最后倒出来 ，有序。 有点order by 样子。

桶的等价优化
count是各个桶的元素个数
count’是count的累计和，那么按照桶从右到左遍历元素时，都可以根据它的左边有多少个元素，以此决定它可以放在输出的数组的何处，当它安置后，它对应的桶的元素个数应该减一。
image.png

稳定性：同样值再排序之后相对次序不变。
用处：int\double等基础类型没用，再非基础类型中有用，比如购物时，先按价格升序，再按好评降序，结果就能找物美价廉的东西。
image.png

冒泡排序可以实现成稳定的 —- 相等时不交换
归并排序可以实现成稳定的 — 相等时先拷贝左边的

快排不是稳定的 - partition不是稳定的。
堆排序不是稳定的—改变

image.png

固定数组实现前缀树

设计Node结点，构建多叉树。
多叉树的头结点是伪结点，作为起始点。
相关查找的方法，都是基于 public Node startsWith_(String prefix){ }方法，其返回值是Node，通过Node可以查询pass和end变量。

  1. class Node{
  2.         // 本质是多叉树
  3.     // 结点信息  
  4.     int pass=0; // 经过该结点的字符串数
  5.     int end=0; // 以该结点结尾的字符串数
  6.     Node[] nexts=new Node[26]; // 子结点索引
  7. }
  8. class Trie {
  10.     Node root; // 伪头结点
  12.     /** Initialize your data structure here. */
  13.     public Trie() {
  14.         root = new Node();  
  15.     }
  17.     /** Inserts a word into the trie. */
  18.     public void insert(String word) {
  19.         if (word == null){
  20.             return;
  21.         }
  22.         char[] arr = word.toCharArray();
  23.         Node cur = root;
  24.         for (int i=0; i < arr.length;i++){ 
  25.             int idx = arr[i] - 'a';
  26.             if (cur.nexts[idx] == null){
  27.                 cur.nexts[idx] = new Node();
  28.             }
  29.             cur = cur.nexts[idx];
  30.             cur.pass++; // 到此一游
  31.         }
  32.         cur.end++; // 到此结束
  33.     }
  35.     /** Returns if the word is in the trie. */
  36.     public boolean search(String word) {
  37.         Node node = startsWith_(word);
  38.         return node != null && node.end > 0;
  39.     }
  41.     /** Returns if there is any word in the trie that starts with the given prefix. */
  42.     public boolean startsWith(String prefix) {
  43.         Node node = startsWith_(prefix);
  44.         return node != null && node.pass > 0;
  45.     }
  47.     // 前缀对应的最后结点，通过它可以知道pass和end信息。
  48.     public Node startsWith_(String prefix){ 
  49.         if (prefix == null){
  50.             return null;
  51.         }
  52.         char[] arr = prefix.toCharArray();
  53.         Node cur = root;
  54.         for (int i=0;i < arr.length;i++){
  55.             int idx = arr[i] - 'a';
  56.             if (cur.nexts[idx] == null){
  57.                 return null;
  58.             }
  59.             cur = cur.nexts[idx];
  60.         }
  61.         return cur;
  62.     }
  64.     // ------------- 
  65.     public void delete(String word){
  66.         if (search(word)){ 
  67.             char[] arr = word.toCharArray();
  68.             Node cur = root;
  69.             for (int i=0;i< arr.length;i++){
  70.                 int idx = arr[i] - 'a';
  71.                 if (--cur.nexts[idx].pass == 0){
  72.                     cur.nexts[idx] = null;
  73.                     return;
  74.                 }
  75.                 cur = cur.nexts[idx];
  76.             }
  77.             cur.end--; 
  78.         }
  79.     }
  80. }
  82. /**
  83.  * Your Trie object will be instantiated and called as such:
  84.  * Trie obj = new Trie();
  85.  * obj.insert(word);
  86.  * boolean param_2 = obj.search(word);
  87.  * boolean param_3 = obj.startsWith(prefix);
  88.  */